【演算法】小白的演算法筆記：堆排序 (,,? ? ?,,)

參考資料

《演算法（第4版）》 — — Robert Sedgewick， Kevin Wayne

什麼是二叉堆

在了解堆排序之前， 最重要的當然是理解二叉堆的概念。 如果我們從零開始探究這個問題：什麼是二叉堆呢？ 那麼這就變成了一個有趣而冗長的一個問題了：

二叉堆：一個堆有序的完全二叉樹， 叫做二叉堆。

在了解二叉堆前， 先讓我們理解下「堆有序」 和「完全二叉樹」的概念

完全二叉樹

讓我們先從二叉樹談起

二叉樹

從一個根節點開始， 每個節點連接一到兩個子節點，依次向下展開的樹形結構，叫做二叉樹。

滿二叉樹

在二叉樹的基礎上， 除了最後一層節點沒有任何子節點外，每一層的節點都有兩個子節點，且每一層都完全填滿的二叉樹，叫做滿二叉樹。在外形上看，就像是一個完整的金字塔的形狀。（從深度和節點數的關係上看，一顆深度為k且有2^k-1個節點的二叉樹稱為滿二叉樹）

完全二叉樹

對滿二叉樹進行從上至下，從左至右的編號（例如上圖所示的從1到7）。如果一個深度為k,有n個節點的二叉樹，其每個節點都和深度同為k的滿二叉樹的編號1到n的節點在位置上一一對應的話，這個二叉樹，就是完全二叉樹。

作為對比， 看看下圖中左下角和右下角的兩顆樹， 因為按照滿二叉樹的編號排定方式，它們相比起同深度的滿二叉樹而言， 分別在6和3的位置沒有對應的節點，所以不是完全二叉樹

堆有序

對於一個二叉樹，如果它滿足：

1. 任意一個父節點都小於等於它相鄰的所有子節點

2. 任意一個父節點都大於等於它相鄰的所有子節點

這兩種情況都可稱之為堆有序（和二叉搜索樹不同的是，二叉堆的左兒子和右兒子間沒有大小關係）

而堆有序的完全二叉樹， 就叫做二叉堆。

【注意】 在接下來的代碼示例中，我們都將默認採取父節點都大於等於它的所有子節點的二叉堆作為展示

二叉堆的表示方法

二叉堆可以用一個普通的一維數組來表示

按照從上至下，從左至右的編號，把二叉堆節點從1編號到N，以此作為數組下標，放入一個長度為N+1的數組中。那麼就形成了一個用數組表示的二叉堆。例如下面的數組a

要注意的是， a[0]沒有存放任何值！ 數組是從a[1]開始存放的。

二叉堆節點間的位置關係

見上圖圖示， 二叉堆的節點位置（對應數組元素下標）間是有數字上的關係的：

在一個堆中，位置k的節點的父節點的位置是k/2, 而兩個子節點的位置則分別是2k和2k+1。這樣的話，在該二叉堆對應的數組中，我們就可以通過計算數組的下標在堆中上下移動： 從a[k]向上一層就令k等於k/2，向下一層則令k等於2k或者2k+1

也就是說，通過這層數字關係， 我們可以找到任意一個堆中節點的父節點和子節點（如果有的話），並進行比較， 在這層基礎上，我們就可以來設計我們的堆有序化的演算法了。

堆有序化的基本演算法：上浮和下沉

堆排序的核心，就是堆有序化的演算法

而堆有序化的基礎，就是針對單個堆節點的有序化

單個堆節點的有序化有兩種情況：

1. 當某個節點變得比它的父節點更大而被打破（或是在堆底加入一個新元素時候），我們需要由下至上恢復堆的順序
2. 當某個節點的優先順序下降（例如，將根節點替換為一個較小的元素）時，我們需要由上至下恢復堆的順序

實現這兩種有序化的操作，分別叫做「上浮」（swim）和「下沉」 （sink）

基於上面所述，下面我們討論的原始場景是這樣的： 只有一個堆節點是非有序的，而其他堆節點都是有序的。

在這種前提下， 該節點對總體堆的順序破環性只有兩種情況：

1. 該節點比它的父節點大
2. 該節點比它的其中一個兒子節點小

（不可能既比父節點大又比兒子節點小，因為我們假設了前提： 其他節點都是堆有序的）

上浮實現堆有序

對第一種情況：某個節點比它的父節點大，如下圖中位置5上的節點

（在圖中，節點為從A到Z的字母，順序上A最小Z最大）

這個時候我們要做的就是：

1.交換它和父節點（位置2）的值， 即P和T互換（這時P將處在5的位置，因為我們假設了前提「其他堆節點都是有序的」，所以互換位置後P肯定是有序的，不用考慮P的順序問題）

2. 基於1， 我們需要判斷交換後T和新的父節點（S）的大小關係， 如果還是大於父節點，那麼再次交換。 不斷循環，直到小於父節點或者該節點已經位於根節點為止（最終T到達了根節點的位置）

下面是我們的上浮方法（和圖示的字母不同，我們的節點優先順序是用整型數值的大小表示的）

/** * @param a 表示堆的數組 * @param k 堆中的節點位置 */ private void swim (int [] a, int k) { while(k>1&&a[k]>a[k/2]){ // 當該結點存在父節點，且大於父節點的時候 exchange(a, k, k/2); // 交換它和它的父節點值 k = k/2; // 取得父節點的位置 } }

下沉實現堆有序

對第二種情況：某個節點比它的至少一個兒子節點小，如下圖中位置2上的節點

（在圖中，節點為從A到Z的字母，順序上A最小Z最大）

這個時候我們要做的就是：

1. 比較該節點（H）的兩個子節點的大小， 取得那個比較大的子節點的值（圖中S），和該節點交換。 成為父節點的那個較大的子節點， 同時大於原子節點（P）和新的子節點（原父節點H），三個節點間是堆有序的

2. 和1一樣，再次判斷交換後的該節點和新的子節點（N和G）的關係， 不斷循環， 直到大於兩個子節點或者到達了底部的葉子節點為止。

下面是我們的下沉方法：

/** * @param a 表示堆的數組 * @param k 堆中的節點位置 * @param N 堆中節點總數 */ private void sink (int [] a, int k, int N) { while(2*k<=N) { // 當該節點存在至少一個子節點的時候 int j = 2*k; // 取得左兒子的位置 if(j<N&&a[j]<a[j+1]) { j++; } // 取得左兒子和右兒子中的較大者 if(a[k]<a[j]) { // 當該節點的值小於較大的左兒子的時候 exchange(a, k, j); // 交換它和該兒子節點的值 k = j; // 取得該兒子節點的位置 } else { break; } } }

二叉堆的基本操作：插入元素和刪除最大元素

為了更好地理解堆排序的過程，讓我們利用剛才的上浮和下沉方法，實現一下對二叉堆的插入和刪除最大元素這兩個操作。

在這之前要提一下的是，我們把上面的兩個方法：sink (int [] a, int k, int N) 和swim (int [] a, int k)中的N和k提取出來變成Heap類的全局變數，這樣的話， 這兩個方法就簡化成了sink (int k) 和swim (int k)

向堆中插入元素

我們將新元素加到數組末尾， 增加堆的大小並讓這個新元素上浮到合適的位置

如圖所示

代碼：

/** * 向堆中插入值 * @param v 要插入的值 */ public void insert (int v) { a[N+1]= v; // 元素被放入堆的最末端成為新節點 N++; // 增加堆的大小 swim(N); // 對末端節點進行上浮操作使其有序 }

向堆中刪除最大元素

我們從數組頂端刪除最大的元素並將數組的最後一個元素放到頂端， 減小堆的大小並讓這個元素下沉到合適的位置

如圖所示：

代碼如下:

/** * 刪除堆中的最大值， 並且將其返回 * @return 堆節點最大值 */ public int delMax () { if(isEmpty()) return 0; // 當堆為空時， 返回 int max = a[1]; // 取得堆中根節點（最大值） exchange(a, 1, N); // 交換根節點和末端節點（最後一個元素）的值 N--; // 減少堆的大小 （「刪除」完畢） sink(1); // 下沉操作，讓剛放上根節點的新元素下沉到合適的位置 return max; }

Heap類的全部代碼：

public class Heap { /** * N: 記錄二叉堆中的節點總數 * a: 容納二叉堆節點的數組,從a[0]開始存放 */ private int N = 0; private int [] a; /** * @param maxN 創建堆中節點的總數 */ public Heap (int maxN) { a = new int [maxN+1]; } private static void exchange(int [] a , int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } /** * 上浮操作 * @param k 堆中的節點位置 */ private void swim (int k) { while(k>1&&a[k]>a[k/2]){ // 當該結點存在父節點，且大於父節點的時候 exchange(a, k, k/2); // 交換它和它的父節點值 k = k/2; // 取得父節點的位置 } } /** * 下沉操作 * @param k 堆中的節點位置 */ private void sink ( int k ) { while(2*k<=N) { // 當該節點存在至少一個子節點的時候 int j = 2*k; // 取得左兒子的位置 if(j<N&&a[j]<a[j+1]) { j++; } // 取得左兒子和右兒子中的較大者 if(a[k]<a[j]) { // 當該節點的值小於較大的左兒子的時候 exchange(a, k, j); // 交換它和該兒子節點的值 k = j; // 取得該兒子節點的位置 } else { break; } } } /** * 向堆中插入值 * @param v 要插入的值 */ public void insert (int v) { a[N+1]= v; // 元素被放入堆的最末端成為新節點 N++; // 增加堆的大小 swim(N); // 對末端節點進行上浮操作使其有序 } /** * 刪除堆中的最大值， 並且將其返回 * @return 堆節點最大值 */ public int delMax () { if(isEmpty()) return 0; // 當堆為空時， 返回 int max = a[1]; // 取得堆中根節點（最大值） exchange(a, 1, N); // 交換根節點和末端節點（最後一個元素）的值 N--; // 減少堆的大小 （「刪除」完畢） sink(1); // 下沉操作，讓剛放上根節點的新元素下沉到合適的位置 return max; } /** * 判斷堆數組是否為空 */ public boolean isEmpty() { return N == 0; } }

測試代碼：

public class Test { public static void main (String [] args) { // 創建一個能容納10個元素的堆 Heap heap = new Heap(10); int [] array = {2,6,3,9,1,5,4,3,0,2}; // 將數組元素依次放入堆中 for(int i =0; i<array.length;i++) { heap.insert(array[i]); } // 依次刪除堆中的最大元素並輸出 for(int i =0; i<array.length;i++) { System.out.println(heap.delMax()); } }}

輸出：

9 6 5 4 3 3 2 2 1 0

誒.仔細看一下我們有序的輸出，是不是找到了些「排序」的影子呢？

我們上面所學習的堆的基本操作之一——刪除最大元素，使用的Heap.delMax方法的有趣之處在於：每次調用它，都會

1.刪除最大元素

2.返回該最大元素

3.使得剩下的堆中元素重新恢復有序

這樣一來，依次刪除返回的就是最大值，第二大值，第三大值...這樣一來不就得到了有序的數組了嗎？ 下面就讓我們來看看堆排序

堆排序

堆排序分為兩個階段：1.堆的構造 2.下沉排序

在堆的構造階段，我們把原始數組重新組織安排進一個堆中，也就是讓這個數組實現堆有序（注意「數組堆有序」 ≠ 「數組有序」！！）

而在下沉排序階段，我們從堆中按遞減順序取得所有元素並得到排序結果。 （類似Heap.delMax）

堆的構造階段

根據前面所講的知識，我們可以猜測， 將堆無序的數組變成堆有序的數組可以有由兩種不同的操作完成： 第一種是使用「上浮」實現堆有序， 第二種是使用「下沉」實現堆有序。

而這兩種方式的效率是不一樣的： 因為「下沉」需要遍歷的節點數比「上浮」需要遍歷的節點數少了一半

1.對上浮排序，我們需要對數組從左向右（或者說對堆從上到下）進行遍歷， 依次保證前兩個元素堆有序， 前三個元素堆有序...... 直到最後一個元素，如圖：

2.而「下沉」實現排序的話，我們需要對數組從右向左（或者說對堆從下到上，但不是最下而是中間）進行遍歷

但是！ 因為最下方的葉子節點沒有子節點，所以不需要排序！ 而需要排序的節點（有子節點的節點）佔N/2 (假設N為節點總數的話)， 所以如下圖所示：

所以說，下沉什麼的最棒了！！！

接下來我們的堆排序是以下沉（sink）為基礎進行的, 有興趣的話大家也可以用上浮實現一下哦

堆的構造代碼：

int N = a.length; // 取得節點總數for(int i=N/2;i>0; i--) { sink(a, i, N); // 對所有父節點，從最後一個父節點到根節點，依次下沉排序}

【注意】不要寫成int N = a.length-1; 因為雖然我們之前寫的二叉堆是忽略了a[0]的(堆節點數N = a.length - 1 )，但這是待排序的數組，當然不能忽略a[0]; (堆節點數N = a.length)

圖示如下：

把構造完畢（實現堆有序）之後，我們就要將「堆有序」的數組轉化為「有序」的數組，這一階段被稱為下沉排序

下沉排序階段

依次把最大的數組元素移到數組的最右端， 依次填充a[N-1], a[N-2]...直到a[0]

while(N>1){ exchange(a, 1, N); // 將數組中最大的元素放到數組後端 N--; // 將最大的節點元素移出堆 sink(a, 1, N); // 下沉操作，再次實現堆有序}

如圖所示：

兩個階段的總代碼：

/** * 堆排序方法 * @param a 待排序數組 */ public static void sort(int [] a) { // 堆的構造階段 int N = a.length; // 取得節點總數 for(int i=N/2;i>0; i--) { sink(a, i, N); // 對所有父節點，從最後一個父節點到根節點，依次下沉排序 } // 到這裡數組已經完全堆有序 // 下沉排序階段 while(N>1){ exchange(a, 1, N); // 將數組中最大的元素放到數組後端 N--; // 將最大的節點元素移出堆 sink(a, 1, N); // 下沉操作，再次實現堆有序 } }

最後要說明一下，在堆排序中，我們的exchange方法和less方法要減1， 因為相比起二叉堆的使用中忽略了a[0], 而實際需要排序的數組當然是有a[0]的呀：

/** * 交換兩個數組元素的值 * 注意！ 不同於一般的exchange, 這裡的i和j要減1！ */ private static void exchange(int [] a , int i, int j) { int temp = a[i-1]; a[i-1] = a[j-1]; a[j-1] = temp; } /** * 比較i和j下標的數組元素的大小 * 注意！ 不同於一般的less, 這裡的i和j要減1！ */ private static boolean less (int [] a, int i, int j) { return a[i-1]-a[j-1]<0 ? true : false; }

堆排序類HeapSort的全部代碼：

public class HeapSort { /** * 交換兩個數組元素的值 * 注意！ 不同於一般的exchange, 這裡的i和j要減1！ */ private static void exchange(int [] a , int i, int j) { int temp = a[i-1]; a[i-1] = a[j-1]; a[j-1] = temp; } /** * 比較i和j下標的數組元素的大小 * 注意！ 不同於一般的less, 這裡的i和j要減1！ */ private static boolean less (int [] a, int i, int j) { return a[i-1]-a[j-1]<0 ? true : false; } /** * 下沉操作 * @param a 待排序數組 * @param k 堆中的節點位置 * @param N 堆中的節點總數 */ private static void sink (int [] a, int k, int N) { while(2*k<=N) { // 當該節點存在至少一個子節點的時候 int j = 2*k; // 取得左兒子的位置 if(j<N&&less(a, j, j+1)) { j++; } // 取得左兒子和右兒子中的較大者 if(less(a, k, j)) { // 當該節點的值小於較大的左兒子的時候 exchange(a, k, j); // 交換它和該兒子節點的值 k = j; // 取得該兒子節點的位置 } else { break; } } } /** * 堆排序方法 * @param a 待排序數組 */ public static void sort(int [] a) { // 堆的構造階段 int N = a.length; // 取得節點總數 for(int i=N/2;i>0; i--) { sink(a, i, N); // 對所有父節點，從最後一個父節點到根節點，依次下沉排序 } // 到這裡數組已經完全堆有序 // 下沉排序階段 while(N>1){ exchange(a, 1, N); // 將數組中最大的元素放到數組後端 N--; // 將最大的節點元素移出堆 sink(a, 1, N); // 下沉操作，再次實現堆有序 } }}

測試代碼：

public class Test { public static void main (String [] args) { int [] array = {3,0,8,9,1,5,4,2,7,1,2}; HeapSort.sort(array); for(int i=0;i<array.length;i++) { System.out.println(array[i]); } }}

輸出：

0 1 1 2 2 3 4 5 7 8 9