Explanation and Java version implementation of heap sort algorithm

Heap is an important structure in data structures. If you understand the concept and operation of "heap", you can quickly master heap sorting.

The concept of heap
Heap is a special complete binary tree. If the value of all nodes in a complete binary tree is not less than its child nodes, it is called a large root heap (or large top heap); if the value of all nodes is not greater than its child nodes, it is called a small root heap (or small top heap). heap).
In the array (the root node is stored in the 0 subscript), it is easy to get the following formula (these two formulas are very important):
1. The node with the subscript i, the parent node coordinates are ( i-1)/2;
2. For the node whose subscript is i, the coordinates of the left child node are 2*i+1 and the right child node is 2*i+2.

Creation and maintenance of heap
Heap can support a variety of operations, but now we are only concerned about two questions:
1. Given an unordered array, how to establish it as a heap?
2. After deleting the top element of the heap, how to adjust the array into a new heap?
Let’s look at the second question first. Assume we already have a large root pile ready to go. Now we've deleted the root element, but haven't moved any other elements. Think about what happens: the root element is empty, but the other elements still maintain the heap nature. We can move the last element (codename A) to the position of the root element. If it is not a special case, the nature of the heap is destroyed. But this is only because A is smaller than one of its children. Therefore, we can swap the positions of A and this sub-element. If A is larger than all its sub-elements, the heap is adjusted; otherwise, the above process is repeated, and the A element continues to "sink" in the tree structure until the appropriate position is reached, and the array regains its heap properties. The above process is generally called "screening", and the direction is obviously top-down.
The same is true for deleting an element, and the same is true for inserting a new element. The difference is that we put the new element at the end and then compare it with its parent node, that is, bottom-up filtering.
So, how to solve the first problem?
Many of the data structure books I have read filter down from the first non-leaf node until the root element is filtered. This method is called "screening method" and requires looping to screen n/2 elements.
But we can also learn from the idea of ​​​​"making something out of nothing". We can treat the first element as a heap and keep adding new elements to it. This method is called "insertion method" and requires the insertion of (n-1) elements in a loop.
Because the filtering method and the insertion method are different, the heaps they create for the same data are generally different.

After having a general understanding of the heap, heap sorting is a matter of course.

Algorithm Overview/Ideas
We need an ascending sequence, what should we do? We can build a min-heap and then output the root element each time. However, this method requires additional space (otherwise it will cause a large number of elements to be moved, and its complexity will soar to O(n^2)). What if we need to sort in place (i.e. O(n) space complexity is not allowed)?
There is a way. We can build a maximum heap, and then we output it backwards, outputting the maximum value at the last position, and outputting the second-largest value at the last position... Since the largest element output each time will free up the first space, we can just place Such elements require no additional space. Pretty idea, isn't it?

public class HeapSort {
  
  public static void main(String[] args) {
    int[] arr = { 50, 10, 90, 30, 70, 40, 80, 60, 20 };
    System.out.println("排序之前：");
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
  
    // 堆排序
    heapSort(arr);
  
    System.out.println();
    System.out.println("排序之后：");
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
  }
  
  /**
   * 堆排序
   */
  private static void heapSort(int[] arr) { 
    // 将待排序的序列构建成一个大顶堆
    for (int i = arr.length / 2; i >= 0; i--){ 
      heapAdjust(arr, i, arr.length); 
    }
      
    // 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
    for (int i = arr.length - 1; i > 0; i--) { 
      swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
      heapAdjust(arr, 0, i); // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
    }
  }
  
  /**
   * 构建堆的过程
   * @param arr 需要排序的数组
   * @param i 需要构建堆的根节点的序号
   * @param n 数组的长度
   */
  private static void heapAdjust(int[] arr, int i, int n) {
    int child;
    int father; 
    for (father = arr[i]; leftChild(i) < n; i = child) {
      child = leftChild(i);
        
      // 如果左子树小于右子树，则需要比较右子树和父节点
      if (child != n - 1 && arr[child] < arr[child + 1]) {
        child++; // 序号增1，指向右子树
      }
        
      // 如果父节点小于孩子结点，则需要交换
      if (father < arr[child]) {
        arr[i] = arr[child];
      } else {
        break; // 大顶堆结构未被破坏，不需要调整
      }
    }
    arr[i] = father;
  }
  
  // 获取到左孩子结点
  private static int leftChild(int i) {
    return 2 * i + 1;
  }
    
  // 交换元素位置
  private static void swap(int[] arr, int index1, int index2) {
    int tmp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = tmp;
  }
}

For more explanations of the heap sort algorithm and articles related to Java version implementation, please pay attention to the PHP Chinese website!