第六章 堆排序

第六章 堆排序

堆排序是一種原地排序演算法：在任何時候數組只有常數個元素存儲在輸入數組之外

（二叉）堆數據結構是一種數組對象。也就是說所有元素都在數組中存儲。同時堆可以視作一顆完全二叉樹。換言之堆實質是數組，但是根據一定的邏輯關係可以將其視作一顆二叉樹。

第一個問題是數組的元素位置和樹的結點位置對應關係

可以看出數組的元素是依次放入樹中：數組第一個元素在根節點；樹的第二層能放兩個元素，所以數組第二個元素和第三個元素放入，以此類推。

第二個問題是父節點和左右結點的關係問題

觀察樹發現父節點在數組位置總是左結點的二倍，右結點位置是左結點位置+1：例如上圖中根節點14在數組位置是2，左結點8在數組位置是2*2=4，右結點7在數組位置是4+1=5

第三個問題是實現最大堆

最大堆：根節點元素值>=葉子值

實現最大堆有兩種方法，第一種是比較笨拙的實現但是很容易理解，第二種是書中提到的思路

第一種思路遞推式可寫作MAX_HEAP(i)=MAX_HEAP(2i)+MAX_HEAP(2i+1)，其中MAX_HEAP(i)函數實現對父節點、左葉、右葉做比較（即數組元素對應位置是i、2i、2i+1）選出最大的作為父節點，然後對左葉與右葉使用MAX_HEAP函數。這樣的實現花費時間且消耗大量棧。

第二種思路是書中所提及的方法，首先要實現一個「不完全」的最大堆函數MAX_HEAPIFY

思路是對父節點、左葉、右葉做比較，如果父節點最大程序結束，如果父節點不為最大，則與最大值結點交換值，之後對被交換的結點繼續使用函數。舉例說明：4左子樹根14右子樹根7，交換之，之後從左子樹根繼續使用函數。（或許有人問為什麼不從根節點開始，因為從根節點開始根據函數定義直接結束，而且這個程序忽略了一種情況，它只遞歸交換的節點，如果另一個節點的向下分支有存在不匹配情況就GG，所以這是一個「不完全」實現）

因為MAX_HEAPIFY函數不完全，所以我們只需要對每一個節點使用此函數一定能保證實現最大堆（這樣此函數的盲點也沒有忽略），但是我們注意到樹的葉對應數組元素位置為（結點個數）/2+1（上圖中的樹的葉是6到10），所以我們只需要對位置為1至（結點個數）/2調用MAX_HEAPIFY函數即可。

第四個問題：堆排序演算法

當建成最大堆時，最大元素一定是最頂的根節點（數組元素第一個）。將根節點與數組最後一個元素交換，這樣最大值歸位；之後對剩餘元素的二叉樹實現最大堆，最大值為數組第一個元素，與數組倒數第二個元素交換，次大元素歸位，以此類推。

第五個問題：常見應用之一——優先順序隊列

設想一個場景：計算機每時每刻都在添加Or執行任務，每個任務都記錄了優先順序，當一個任務結束Or中斷，會選出最高優先順序的任務執行，所以一個最大優先順序隊列需要支持以下操作：INSERT(S, x)（將任務x插入隊列S中）

MAXIMUM(S)（從隊列S中返回優先順序最大元素）

EXTRACT-MAX(S)（從隊列S中返回優先順序最大元素並將此元素彈出）

INCREASE-KEY(S, x, k)（將隊列S中的任務x的關鍵字提升至k，k不能小於原x的關鍵字）

此時數組的元素可以簡化為一個結構體，元素為一個記錄優先順序的變數和一個指向任務的句柄，排序等操作是針對結構體中的優先順序變數而言的。

MAXIMUM(S)實現實質是返回數組第一個元素

EXTRACT-MAX(S)：將數組第一個元素返回，然後去除第一個元素將剩餘元素實現最大堆

INCREASE-KEY(S, x, k)：首先將任務x的關鍵字增加至k，然後與其父節點比較，如果大於父節點交換之，之後繼續和新的父節點比較，依次往複直到達到最大堆條件為止。

INSERT(S, x)：首先擴充堆（數組），然後調用INCREASE-KEY(S, x, k)設置新空間的關鍵字並調整整個堆達到最大堆。

推薦閱讀：