堆是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。

對于堆的操作通常需要以下3個步驟：

最大堆調整（Max Heapify）：將堆的末端子節點作調整，使得子節點永遠小于父節點

創建最大堆（Build Max Heap）：將堆中的所有數據重新排序

堆排序（HeapSort）：移除位在第一個數據的根節點，并做最大堆調整的遞歸運算。

C代碼實現

代碼看起來比較抽象，將代碼運行時數據交換的過程打印出來，然后結合二叉樹的圖形來分析，就會比較好理解了。代碼運行過程中數據交換過程如下：

為了方便觀看這里使用二叉樹圖形生成軟件，通過二叉樹圖形來觀察數據交換過程。二叉樹圖形生成使用的是一個在線生成網站：mshang.ca/syntree 后面所有的二叉樹圖形都使用此軟件生成。

代碼一開始首先打印出原始數據

數組元素 0 8 1 5 4 3 7 9 2 6 將這10個數據在網站上使用公式生成二叉樹的圖表，軟件界面如下：

首先將數組從上至下按順序排列，轉換成二叉樹。

公式：0［8 ［5 9［2］］［4［6］］］ ［1［3］ ［7 ］］］

轉換成二叉樹之后，需要讓這個無序堆變成最大堆，也就是每個堆都實現父節點的值大于任何一個子節點值。從最后一個堆開始，依次比較父節點和子節點的值，如果子節點值大于父節點值，就需要交換。

創建最大堆： 6為最后一個子節點，所以從6開始依次和父節點比較，如果子節點大于父節點，就需要交換子節點和父節點的位置。從設備樹圖形中可以看出，子節點6大于父節點4，所以需要交換子節點的父節點的位置。

公式：0［8 ［5 9［2］］［6［4］］］ ［1［3］ ［7 ］］］

交換 6 和4

6交換完成后，接下來依次向前比較其他子節點，6前面的節點是2，2小于父節點5，繼續向前查找子節點9，子節點9大于父節點5，所以就交換9和5的位置。

公式：0［8 ［9 5［2］］［6［4］］］ ［1［3］ ［7 ］］］

交換9和5

接下來繼續向前查找，發現子節點7大于父節點1，繼續交換。

公式：0［8 ［9 5［2］］［6［4］］］ ［7［3］ ［1 ］］］

交換7和1

繼續向前查找發現子節點9大于父節點8，交換位置。

公式：0［9 ［8 5［2］］［6［4］］］ ［7［3］ ［1 ］］］

交換9和8

繼續比較其他節點

公式：9［0 ［8 5［2］］［6［4］］］ ［7［3］ ［1 ］］］

交換9和0

公式：9［8 ［0 5［2］］［6［4］］］ ［7［3］ ［1 ］］］

交換8和0

公式：9［8 ［5 0［2］］［6［4］］］ ［7［3］ ［1 ］］］

交換5和0

此時最大堆已經創建完成，此時根節點的數字9就是數組中的最大值。

代碼中打印出來的數據順序和通過二叉樹圖形分析出來的順序完全一樣。此時最大堆調整已經完成了。接下來就需要開始堆排序，依次將根節點的數據存放到最后一個節點，形成一個有序堆。

堆排序（最大堆調整）

首先交換數組中第一個元素，和排序好的前一個元素位置。此時數組中的第一個元素是9，排序完成之后最后一個元素是4，交換9和4.

公式：4［8 ［5 0［2］］［6［9］］］ ［7［3］ ［1 ］］］

交換9和4

交換完成后，此時最大值9所在的底部位置就成為了有序區，有序區之后就不會參與任何對比。接下來繼續調整父節點和子節點，確保父節點要大于子節點。

公式：8［4 ［5 0［2］］［6［9］］］ ［7［3］ ［1 ］］］

交換8和4

公式：8［6 ［5 0［2］］［4［9］］］ ［7［3］ ［1 ］］］

交換6和4

此時數字8稱為了根節點，是目前無序區中的最大值，將8和底部區的2交換，將當前最大值8放到有序區中。

公式：2［6 ［5 0［8］］［4［9］］］ ［7［3］ ［1 ］］］

交換8和2

此時8已經存放到了有序區中，此后就不參與任何交換了。此時2變為根節點后，需要在重新調整一次節點，確保父節點大于子節點。

公式：7［6 ［5 0［8］］［4［9］］］ ［2［3］ ［1 ］］］

交換7和2

公式：7［6 ［5 0［8］］［4［9］］］ ［3［2］ ［1 ］］］

交換3和2

此時數字7變為根節點，是無序區間的最大值。需要將根節點的數字移動到有序區中。

將根節點7和0交換位置。

公式：0［6 ［5 7［8］］［4［9］］］ ［3［2］ ［1 ］］］

交換7和0

接下來重新調整節點 公式：6［0 ［5 7［8］］［4［9］］］ ［3［2］ ［1 ］］］

交換6和0

公式：6［5 ［0 7［8］］［4［9］］］ ［3［2］ ［1 ］］］

交換5和0

此時6變為了根節點，是無序區間的最大值。

將根節點和有序區間的前一個數字交換，也就是1和6需要交換。

公式：1［5 ［0 7［8］］［4［9］］］ ［3［2］ ［6 ］］］

交換6和1

接下來重新調節一次節點

公式：5［1 ［0 7［8］］［4［9］］］ ［3［2］ ［6 ］］］

交換5和1

公式：5［4 ［0 7［8］］［1［9］］］ ［3［2］ ［6 ］］］

交換4和1

此時5變成的根節點，需要將5移動到有序隊列中去。

接下來需要交換根節點5和無序節點2的位置

公式：2［4 ［0 7［8］］［1［9］］］ ［3［5］ ［6 ］］］

交換5和2

重新調整節點位置

公式：4［2 ［0 7［8］］［1［9］］］ ［3［5］ ［6 ］］］

交換4和2

此時4是無序列表中的最大值，需要交換4和1的位置

公式：1［2 ［0 7［8］］［4［9］］］ ［3［5］ ［6 ］］］

交換4和1

重新調整節點位置

公式：9［2 ［0 6［7］］［3［8］］］ ［1［4］ ［5 ］］］

交換3和1

此時3為無序列表中最大值，需要交換3和0的位置。

公式：0［2 ［3 7［8］］［4［9］］］ ［1［5］ ［6 ］］］

交換3和0

交換完成后重新調整節點位置 公式：9［0 ［2 6［7］］［3［8］］］ ［1［4］ ［5 ］］］

交換2和0

此時2變成了無序列表中最大值，1為有序列表的前一個值，交換2和1的位置。

公式：1［0 ［3 7［8］］［4［9］］］ ［2［5］ ［6 ］］］

交換2和1

此時1是根節點，無序列表中就剩0一個數字了，交換1和0。

公式：0［1 ［3 7［8］］［4［9］］］ ［2［5］ ［6 ］］］

交換1和0

這是0變成了根節點，而其他的所有數字都在有序列表中，無序列表中已經沒有數字了，此時說明排序完成。

可以看出最好、最壞、一般情況下數據移動的次數和方法基本都差不多。

接下來隨機生成10000個數據，看看排序需要多長時間。

編輯：jq