八大排序（四）：堆排序

水深无声 2022-05-25 03:48 141阅读 0赞

源码地址：  
[https://github.com/TimePickerWang/aimed-at-offer/blob/master/java%E6%BA%90%E7%A0%81/Sort.java][https_github.com_TimePickerWang_aimed-at-offer_blob_master_java_E6_BA_90_E7_A0_81_Sort.java]

## 堆的定义 ##

堆是具有以下性质的完全二叉树：  
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆  
每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆  
如下图所示：

![这里写图片描述][70]

对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

![这里写图片描述][70 1]

以上数组从逻辑上讲就是一个堆结构，用简单的公式来描述一下堆的定义就是：  
大顶堆：arr\[i\] >= arr\[2i+1\] && arr\[i\] >= arr\[2i+2\]  
小顶堆：arr\[i\] <= arr\[2i+1\] && arr\[i\] <= arr\[2i+2\]

## 堆排序 ##

堆排序的算法过程如下(假设有n各元素)：  
1.先将初始文件R\[0\]，R\[1\]……R\[n-1\]建成一个大根堆。建堆是不断调整堆的过程，从最后一个非叶子结点(n/2-1)开始开始调整，一直到第一个节点  
2.再将关键字最大的记录R\[0\]（即堆顶）和无序区的最后一个记录R\[n-1\]交换，由此得到新的无序区R\[0\]，R\[1\]……R\[n-2\]和有序区R\[n-1\]，且满足R\[0\]，R\[1\]…R\[n-2\]≤R\[n-1\]  
3.由于交换后新的根R\[0\]可能违反堆性质，故应将当前无序区R\[0\]，R\[1\]……R\[n-2\]调整为大根堆 。然后再将调整后关键字最大的记录R\[0\]和该区间的最后一个记录R\[n-2\]交换，由此得到新的无序区R\[0\]，R\[1\]……R\[n-3\]和有序区R\[n-2\]，R\[n-1\]，且仍满足关系R\[0\]，R\[1\]……R\[n-3\]≤R\[n-2\]……R\[n-1\]，同样要将R\[0\]，R\[1\]……R\[n-3\]调整为大根堆。  
……  
直到无序区只有一个元素为止。

可以结合下面的图更直观的理解（都是从[图解排序算法(三)之堆排序][Link 1]里扣出来的，原文写的很棒，所以我直接搬来了，见谅）

**首先构造最大堆**  
1.假设给定无序序列结构如下  
![这里写图片描述][70 2]  
2.此时从最后一个非叶子结点开始（最后一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的值为6结点），从左至右，从下至上进行调整。由于9>6且9>5，所以将9和父节点6两个节点交换。  
![这里写图片描述][70 3]  
3.第二个非叶节点4的两个子节点的值分别为9和8，由于9>4且9>8,所以将9和父节点4交换。  
![这里写图片描述][70 4]  
4.这时，交换导致了子树\[4,5,6\]结构混乱，继续调整，\[4,5,6\]中6最大，交换4和6。  
![这里写图片描述][70 5]  
此时，我们就将一个无需序列构造成了一个大顶堆。

**然后将堆顶元素与末尾元素进行交换，使末尾元素最大。交换继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建，直到只有一个元素为止。**

1.将堆顶元素9和末尾元素4进行交换  
![这里写图片描述][70 6]  
2.重新调整结构，使其满足最大堆定义  
![这里写图片描述][70 7]  
3.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.  
![这里写图片描述][70 8]  
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序  
![这里写图片描述][70 9]

根据以上过程，堆排序的代码如下

堆排序：

// 堆排序
        public float[] heapSort(float[] array) {
            // 构建最大堆
            for (int i = array.length / 2 - 1; i >= 0; i--) {
                adjustHeap(array, i, array.length);
            }
            // 交换堆顶元素和末尾元素，并在交换之后调整堆结构
            for (int j = array.length - 1; j > 0; j--) {
                float temp = array[j];
                array[j] = array[0];
                array[0] = temp;
                adjustHeap(array, 0, j);
            }
            return array;
        }
    
        // 调整堆结构
        public void adjustHeap(float[] array, int i, int length) {
            float temp = array[i];
            for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
                if (k + 1 < length && array[k] < array[k + 1]) {
                    k++;
                }
                if (array[k] > temp) {
                    array[i] = array[k];
                    i = k;
                } else {
                    break;
                }
                array[i] = temp;
            }
        }

堆排序的平均时间复杂度是O(nlogn)。

ref:  
[堆排序][Link 2]  
[图解排序算法(三)之堆排序][Link 1]

[https_github.com_TimePickerWang_aimed-at-offer_blob_master_java_E6_BA_90_E7_A0_81_Sort.java]: https://github.com/TimePickerWang/aimed-at-offer/blob/master/java%E6%BA%90%E7%A0%81/Sort.java
[70]: /images/20220525/ad9d89afc2dd4473aeafea6e1b475221.png
[70 1]: /images/20220525/c24e0b1d19dc49f1af9b3f232b887831.png
[Link 1]: http://www.cnblogs.com/chengxiao/p/6129630.html
[70 2]: /images/20220525/c8b86ab5799e453aaf64b1d46e994731.png
[70 3]: /images/20220525/1f20f08e3bf041ab8dc536d33ab7c4dd.png
[70 4]: /images/20220525/8633a3bc02c84c04b4c44eab63191e8c.png
[70 5]: /images/20220525/ff9b2b509b15474585bbc85b8007c5de.png
[70 6]: /images/20220525/c03d36ce7fb54b898d4cb98c73f8672b.png
[70 7]: /images/20220525/ddd8f4baf08b4b6fbcf9e161df04b6ac.png
[70 8]: /images/20220525/ca6c4b1c5ff74ffe95a11dea1a751c3c.png
[70 9]: /images/20220525/00433dae2185493caea9f8b36066cbfc.png
[Link 2]: https://baike.baidu.com/item/%E5%A0%86%E6%8E%92%E5%BA%8F/2840151?fr=aladdin