圖解堆排序（二）堆的基本操作

圖解堆排序（一）什麼是堆和堆的性質

1。 引言

在上一篇文章中，我們瞭解到堆排序面臨兩大主要問題：

1。 將一個序列構造為一個大頂堆；

2。 將一個大頂堆的根結點取出後，調整它的剩餘結點以使它們形成一個新的大頂堆。

第一個問題也可以透過第二個問題的解決方法進行解決，因此我們先講解第二個問題。

2。 堆調整

2。1 演算法概述

將一個堆的根結點取出後，對它的剩餘結點進行調整以使它們重新形成一個堆的過程稱為

堆調整

。這裡我們以大頂堆為例介紹堆調整的過程，而小頂堆調整的過程是類似的。

取出一個大頂堆的根結點後，將該大頂堆最後的那個結點移到根結點的位置，作為新的根結點，如圖1所示。此時這個新完全二叉樹的左右子樹依舊是大頂堆，只是新的根結點可能不滿足大頂堆的要求。這也是大頂堆調整的前提條件，即一個完全二叉樹的左右子樹都是大頂堆，而只有根結點可能不滿足大頂堆的要求。

假設此時新根結點滿足大頂堆的要求，即它的值大於等於它的左右孩子結點的值，那麼這棵新完全二叉樹就已經是一個大頂堆了，那麼調整結束。

但在圖1中，新根結點的值是39，小於它的左右孩子結點，不滿足大頂堆的要求（圖中用紅色表示這一情況）。所以，還需要對該根結點進行調整。

圖1 讓最後一個結點成為新的根結點

選擇該根結點的孩子結點中較大的那個，將它和該較大的孩子結點交換位置，如圖2所示。交換後的新根結點必定是所有結點中最大的那個，因此大於等於它的左右孩子。以未交換的那個孩子結點為根的子樹不受影響，它依舊是一個大頂堆；而另一個子樹（現在以原根結點為根）可能不再是一個大頂堆了。

在圖2中，將根結點（值為39）和它的右孩子（值為83）進行交換，新根結點（值為83）大於等於它的左右孩子。左子樹（以值77為根）不受影響，依舊是一個大頂堆。而右子樹（現在以值39為根）現在不再是一個大頂堆了，因為值39小於它的左孩子結點的值。

圖2 大頂堆調整過程1

該右子樹之前是一個大頂堆，只是交換了它的根結點，所以它的左右子樹依舊是大頂堆，而只有它的新根結點現在不滿足大頂堆的要求。因此，這棵子樹現在也滿足大頂堆調整的前提條件，我們需要對該子樹的新根結點再次進行調整。該子樹的調整過程類似於前一步調整，如圖3所示。

圖3 大頂堆調整過程2

在圖3中，該子樹的根結點（值為39）的較大孩子結點是它的左孩子（值為61），因此將這兩個結點交換位置。交換後，值為39的結點形成一棵只有一個結點的完全二叉樹，也就是它沒有左右孩子，因此它滿足大頂堆的要求。至此，整棵完全二次樹也是一個大頂堆了，因此調整過程結束。

2。2 演算法實現

我們用C語言實現大頂堆調整演算法，實現程式碼直接對應我們上面的演算法講解，並且程式碼中給出了非常詳細的註釋，因此程式碼應該是很好理解的。

該實現中有一個注意點，那就是當我們交換父結點和它的較大孩子結點的時候，只是把孩子結點的值寫到了父結點的位置而沒有把父結點的值寫到孩子結點上，這也正是為什麼下面程式碼中的第56行程式碼會被註釋掉。

這是因為對父結點進行一次調整後可能還要繼續進行多次調整，這樣它剛剛交換到的位置又會馬上被它的新孩子結點（較大的那個）覆蓋。因此，只需要最後時刻再將該父結點一次性地寫到它最終調整到的位置上就行了，這樣可以減少一些消耗；下面程式碼中第61行程式碼的作用正是為了實現這一目的。

3。 堆構造

3。1 演算法概述

要將一個序列構造為堆，我們只需要在該序列對應的完全二叉樹中按從下至上和從右至左的順序反覆地對每一棵子樹運用堆調整的演算法就可以了。從原序列的最後一個元素開始向前遍歷每一個元素，每遍歷到一個元素都對以該元素為根結點的子樹進行大頂堆調整。因為是從後向前遍歷，因此每遍歷到一個元素時，它的左右子樹都已經是大頂堆了，因此以該元素為根的完全二叉樹是可以直接使用大頂堆調整演算法的。在對根結點（序列中的第一個元素）應用完大頂堆調整之後，原序列就被構建成了一個大頂堆了。

因為葉子結點沒有孩子結點，因此以葉結點為根的子樹本身就是大頂堆，因此我們可以從最後一個內部結點開始向前遍歷。而最後一個內部結點必定是最後一個結點（它的下標為n-1）的父結點，所以最後一個內部結點的下標為（n-1-1）/2。

我們還是用一個例子來展示大頂堆構造的完整過程，假設原序列為［35， 52， 61， 39， 29， 96， 83， 43， 77］。我們首先將該序列表示成完全二叉樹的形式，因為該樹共有9個結點，因此最後一個內部結點的下標為3。我們對以編號是3的結點為根的子樹進行大頂堆調整，如圖4所示，圖中的虛線框表示我們正對其進行調整的子樹。

圖4 對編號是3的結點進行大頂堆調整

然後對以編號是2的結點為根的子樹進行大頂堆調整，如圖5所示。

圖5 對編號是2的結點進行大頂堆調整

再對以編號是1的結點為根的子樹進行大頂堆調整，如圖6所示。

圖6 對編號是1的結點進行大頂堆調整

最後對以編號是0的結點為根的子樹（它其實也是整棵完全二叉樹）進行大頂堆調整，如圖7所示。至此，整個序列就被構造成了一個大頂堆了。

圖7 對編號是0的結點進行大頂堆調整

3。2 演算法實現

我們同樣用C語言來實現構造大頂堆的演算法，實現程式碼還是直接對應我們上面的演算法講解，並且在程式碼中給出了非常詳細的註釋。因為堆構造是建立在堆調整的基礎上的，因此這裡需要呼叫第2節中實現的heapAdjust（）函式。

該實現程式碼中有一個地方需要注意，我們在第2節實現heapAdjust（）函式的時候說過，它的第三個引數end是要調整的完全二叉樹（代表一個要調整的大頂堆）的最後一個結點在序列中的下標。那麼當我們對不同的子樹進行調整時，傳遞給heapAdjust（）函式的第三個引數應該是該子樹的最後一個結點在序列中的下標。

但是看下面程式碼中的第20行，我們每次呼叫heapAdjust（）函式時傳遞的第三個引數都是n-1，它其實是整個序列中最後一個元素的下標。之所以這樣做，是基於以下兩點原因：

1。 每次都要計算當前子樹的最後一個結點的下標比較麻煩，而且需要額外的開銷；

2。 將最後一個引數統一設定為n-1在所有子樹中都沒有引入多餘的結點，此時該子樹的結構是不變的，因此調整結果是正確的。假設這一操作為某個子樹引入了一個多餘的結點，那麼該結點之前也必定不存在於整棵樹（代表整個序列）中，那麼引入後它的下標應該大於n-1；但我們實際已知所有結點的下標都小於等於n-1，所以假設不成立。

（完）