堆排序

堆的定义

堆（二叉堆）可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。
如下图，是一个堆和数组的相互关系

Paste_Image.png

父子节点的运算关系

对于给定的某个结点的下标 i，可以很容易的计算出这个结点的父结点、孩子结点的下标：
Parent(i) = floor(i/2)，i 的父节点下标
Left(i) = 2i，i 的左子节点下标
Right(i) = 2i + 1，i 的右子节点下标

最大堆最小堆

二叉堆一般分为两种：最大堆和最小堆。

最大堆中的最大元素值出现在根结点（堆顶）
堆中每个父节点的元素值都大于等于其孩子结点（如果存在）

最大堆 最大堆
最小堆中的最小元素值出现在根结点（堆顶）
堆中每个父节点的元素值都小于等于其孩子结点（如果存在）

最小堆

堆排序

堆排序就是把最大堆堆顶的最大数与末尾的数交换，然后将末尾的数排除大根堆。然后将剩余的堆继续调整为最大堆，再次将堆顶的最大数与末尾的数交换，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：

基本操作

• Bottom-up reheapify (swim).* If the heap order is violated because a node's key becomes larger than that node's parents key, then we can make progress toward fixing the violation by exchanging the node with its parent. After the exchange, the node is larger than both its children (one is the old parent, and the other is smaller than the old parent because it was a child of that node) but the node may still be larger than its parent. We can fix that violation in the same way, and so forth, moving up the heap until we reach a node with a larger key, or the root.

Paste_Image.png

private void swim(int k) {
   while (k > 1 && less(k/2, k)) {
      exch(k, k/2);
      k = k/2;
   }
}

• Top-down heapify (sink).* If the heap order is violated because a node's key becomes smaller than one or both of that node's children's keys, then we can make progress toward fixing the violation by exchanging the node with the larger of its two children. This switch may cause a violation at the child; we fix that violation in the same way, and so forth, moving down the heap until we reach a node with both children smaller, or the bottom.

Paste_Image.png

private void sink(int k) {
   while (2*k <= N) {
      int j = 2*k;
      if (j < N && less(j, j+1)) j++;
      if (!less(k, j)) break;
      exch(k, j);
      k = j;
   }
}

• Insert. We add the new item at the end of the array, increment the size of the heap, and then swim up through the heap with that item to restore the heap condition.
• Remove the maximum. We take the largest item off the top, put the item from the end of the heap at the top, decrement the size of the heap, and then sink down through the heap with that item to restore the heap condition.
  Paste_Image.png

实现

分为两步，先建堆再进行下沉堆排序。
建堆过程是从末尾节点的孩子开始进行下沉(sink)操作，依次执行直到头结点，此时建成大根堆。
堆排序则是将头结点和尾节点交换，将尾节点从堆中删除，然后对头结点进行下沉操作。

Paste_Image.png

public void heapSort(int[] array, int n) {
    //建堆过程
    for(int i=(array.length-1)/2;i>=0;i--){
        sink(array,i,array.length-1);
    }   
    for(int i=n-1;i>0;i--){
        swap(array,0,i);
        sink(array,0,i-1);
    }   
}
    
private void sink(int[] array,int lo,int hi){
    while(lo*2+1<=hi){
        int left=lo*2+1;
        if(left<hi&&array[left]<array[left+1]) left++;
        if(array[lo]>=array[left])break;
        swap(array,left,lo);
        lo=left;
    }
}