堆的概念

在介紹堆排序之前，首先需要說明一下,，堆是個什么玩意兒,。

堆是一棵順序存儲的完全二叉樹。

其中每個結(jié)點(diǎn)的關(guān)鍵字都不大于其孩子結(jié)點(diǎn)的關(guān)鍵字,，這樣的堆稱為小根堆,。

其中每個結(jié)點(diǎn)的關(guān)鍵字都不小于其孩子結(jié)點(diǎn)的關(guān)鍵字，這樣的堆稱為大根堆,。

舉例來說,，對于n個元素的序列{R0, R1, ... , Rn}當(dāng)且僅當(dāng)滿足下列關(guān)系之一時，稱之為堆：

(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)

(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)

其中i=1,2,…,n/2向下取整; 

如上圖所示,，序列R{3, 8, 15, 31, 25}是一個典型的小根堆,。

堆中有兩個父結(jié)點(diǎn)，元素3和元素8,。

元素3在數(shù)組中以R[0]表示,，它的左孩子結(jié)點(diǎn)是R[1],，右孩子結(jié)點(diǎn)是R[2]。

元素8在數(shù)組中以R[1]表示,，它的左孩子結(jié)點(diǎn)是R[3],，右孩子結(jié)點(diǎn)是R[4]，它的父結(jié)點(diǎn)是R[0],?？梢钥闯觯鼈?strong style="margin: 0px; padding: 0px;">滿足以下規(guī)律：

設(shè)當(dāng)前元素在數(shù)組中以R[i]表示,，那么,，

(1) 它的左孩子結(jié)點(diǎn)是：R[2*i+1];

(2) 它的右孩子結(jié)點(diǎn)是：R[2*i+2];

(3) 它的父結(jié)點(diǎn)是：R[(i-1)/2];

(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。

要點(diǎn)

首先,，按堆的定義將數(shù)組R[0..n]調(diào)整為堆（這個過程稱為創(chuàng)建初始堆），交換R[0]和R[n],；

然后,，將R[0..n-1]調(diào)整為堆，交換R[0]和R[n-1],；

如此反復(fù),，直到交換了R[0]和R[1]為止。

以上思想可歸納為兩個操作：

（1）根據(jù)初始數(shù)組去構(gòu)造初始堆（構(gòu)建一個完全二叉樹,，保證所有的父結(jié)點(diǎn)都比它的孩子結(jié)點(diǎn)數(shù)值大）,。

（2）每次交換第一個和最后一個元素，輸出最后一個元素（最大值）,，然后把剩下元素重新調(diào)整為大根堆,。 

當(dāng)輸出完最后一個元素后，這個數(shù)組已經(jīng)是按照從小到大的順序排列了,。

先通過詳細(xì)的實(shí)例圖來看一下,，如何構(gòu)建初始堆。

設(shè)有一個無序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 },。

構(gòu)造了初始堆后,，我們來看一下完整的堆排序處理：

還是針對前面提到的無序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 來加以說明。

相信,，通過以上兩幅圖,，應(yīng)該能很直觀的演示堆排序的操作處理。 

核心代碼

public void HeapAdjust(int[] array, int parent, int length) {
    int temp = array[parent]; // temp保存當(dāng)前父節(jié)點(diǎn)
    int child = 2 * parent + 1; // 先獲得左孩子
 
    while (child < length) {
        // 如果有右孩子結(jié)點(diǎn),，并且右孩子結(jié)點(diǎn)的值大于左孩子結(jié)點(diǎn),，則選取右孩子結(jié)點(diǎn)
        if (child + 1 < length && array[child] < array[child + 1]) {
            child++;
        }
 
        // 如果父結(jié)點(diǎn)的值已經(jīng)大于孩子結(jié)點(diǎn)的值，則直接結(jié)束
        if (temp >= array[child])
            break;
 
        // 把孩子結(jié)點(diǎn)的值賦給父結(jié)點(diǎn)
        array[parent] = array[child];
 
        // 選取孩子結(jié)點(diǎn)的左孩子結(jié)點(diǎn),繼續(xù)向下篩選
        parent = child;
        child = 2 * child + 1;
    }
 
    array[parent] = temp;
}
 
public void heapSort(int[] list) {
    // 循環(huán)建立初始堆
    for (int i = list.length / 2; i >= 0; i--) {
        HeapAdjust(list, i, list.length - 1);
    }
 
    // 進(jìn)行n-1次循環(huán),，完成排序
    for (int i = list.length - 1; i > 0; i--) {
        // 最后一個元素和第一元素進(jìn)行交換
        int temp = list[i];
        list[i] = list[0];
        list[0] = temp;
 
        // 篩選 R[0] 結(jié)點(diǎn),，得到i-1個結(jié)點(diǎn)的堆
        HeapAdjust(list, 0, i);
        System.out.format("第 %d 趟: \t", list.length - i);
        printPart(list, 0, list.length - 1);
    }
}

算法分析

堆排序算法的總體情況

時間復(fù)雜度

堆的存儲表示是順序的,。因?yàn)槎阉鶎?yīng)的二叉樹為完全二叉樹，而完全二叉樹通常采用順序存儲方式,。

當(dāng)想得到一個序列中第k個最小的元素之前的部分排序序列,，最好采用堆排序。

因?yàn)槎雅判虻臅r間復(fù)雜度是O(n+klog2n),，若k≤n/log2n,，則可得到的時間復(fù)雜度為O(n)。

算法穩(wěn)定性

堆排序是一種不穩(wěn)定的排序方法,。

因?yàn)樵诙训恼{(diào)整過程中,，關(guān)鍵字進(jìn)行比較和交換所走的是該結(jié)點(diǎn)到葉子結(jié)點(diǎn)的一條路徑，

因此對于相同的關(guān)鍵字就可能出現(xiàn)排在后面的關(guān)鍵字被交換到前面來的情況,。 

完整參考代碼

JAVA版本

代碼實(shí)現(xiàn)

以下范例是對上文提到的無序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 進(jìn)行排序,。

 1 package notes.javase.algorithm.sort;
 2  
 3 public class HeapSort {
 4  
 5     public void HeapAdjust(int[] array, int parent, int length) {
 6         int temp = array[parent]; // temp保存當(dāng)前父節(jié)點(diǎn)
 7         int child = 2 * parent + 1; // 先獲得左孩子
 8  
 9         while (child < length) {
10             // 如果有右孩子結(jié)點(diǎn)，并且右孩子結(jié)點(diǎn)的值大于左孩子結(jié)點(diǎn),，則選取右孩子結(jié)點(diǎn)
11             if (child + 1 < length && array[child] < array[child + 1]) {
12                 child++;
13             }
14  
15             // 如果父結(jié)點(diǎn)的值已經(jīng)大于孩子結(jié)點(diǎn)的值,，則直接結(jié)束
16             if (temp >= array[child])
17                 break;
18  
19             // 把孩子結(jié)點(diǎn)的值賦給父結(jié)點(diǎn)
20             array[parent] = array[child];
21  
22             // 選取孩子結(jié)點(diǎn)的左孩子結(jié)點(diǎn),繼續(xù)向下篩選
23             parent = child;
24             child = 2 * child + 1;
25         }
26  
27         array[parent] = temp;
28     }
29  
30     public void heapSort(int[] list) {
31         // 循環(huán)建立初始堆
32         for (int i = list.length / 2; i >= 0; i--) {
33             HeapAdjust(list, i, list.length - 1);
34         }
35  
36         // 進(jìn)行n-1次循環(huán)，完成排序
37         for (int i = list.length - 1; i > 0; i--) {
38             // 最后一個元素和第一元素進(jìn)行交換
39             int temp = list[i];
40             list[i] = list[0];
41             list[0] = temp;
42  
43             // 篩選 R[0] 結(jié)點(diǎn),，得到i-1個結(jié)點(diǎn)的堆
44             HeapAdjust(list, 0, i);
45             System.out.format("第 %d 趟: \t", list.length - i);
46             printPart(list, 0, list.length - 1);
47         }
48     }
49  
50     // 打印序列
51     public void printPart(int[] list, int begin, int end) {
52         for (int i = 0; i < begin; i++) {
53             System.out.print("\t");
54         }
55         for (int i = begin; i <= end; i++) {
56             System.out.print(list[i] + "\t");
57         }
58         System.out.println();
59     }
60  
61     public static void main(String[] args) {
62         // 初始化一個序列
63         int[] array = {
64                 1, 3, 4, 5, 2, 6, 9, 7, 8, 0
65         };
66  
67         // 調(diào)用快速排序方法
68         HeapSort heap = new HeapSort();
69         System.out.print("排序前:\t");
70         heap.printPart(array, 0, array.length - 1);
71         heap.heapSort(array);
72         System.out.print("排序后:\t");
73         heap.printPart(array, 0, array.length - 1);
74     }
75 }

運(yùn)行結(jié)果 

參考資料

《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》（B級第3版）