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

對于堆的操作通常需要以下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個數據，看看排序需要多長時間。

最後用一張動圖來演示堆排序的過程

寫在最後

另外，對現在我們的大多數朋友來說還是學編程技術最重要！栽一棵樹最好的時間是十年前，其次是現在。對于準備學習編程的小夥伴，如果你想更好地提升你的編程核心能力（内功）不妨從現在開始！

編程學習書籍分享：

編程學習視頻分享：

整理分享（多年學習的源碼、項目實戰視頻、項目筆記，基礎入門教程）

歡迎轉行和學習編程的夥伴，利用更多的資料學習成長比自己琢磨更快哦！

想學習C/C 編程，或者對編程感興趣的話可以【私信】筆者領取免費學習資料喲~

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!