堆是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿(mǎn)足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

對(duì)于堆的操作通常需要以下3個(gè)步驟：

最大堆調(diào)整（Max Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)

創(chuàng)建最大堆（Build Max Heap）：將堆中的所有數(shù)據(jù)重新排序

堆排序（HeapSort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算。

C代碼實(shí)現(xiàn)

代碼看起來(lái)比較抽象，將代碼運(yùn)行時(shí)數(shù)據(jù)交換的過(guò)程打印出來(lái)，然后結(jié)合二叉樹(shù)的圖形來(lái)分析，就會(huì)比較好理解了。代碼運(yùn)行過(guò)程中數(shù)據(jù)交換過(guò)程如下：

為了方便觀看這里使用二叉樹(shù)圖形生成軟件，通過(guò)二叉樹(shù)圖形來(lái)觀察數(shù)據(jù)交換過(guò)程。二叉樹(shù)圖形生成使用的是一個(gè)在線(xiàn)生成網(wǎng)站：mshang.ca/syntree 后面所有的二叉樹(shù)圖形都使用此軟件生成。

代碼一開(kāi)始首先打印出原始數(shù)據(jù)

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

首先將數(shù)組從上至下按順序排列，轉(zhuǎn)換成二叉樹(shù)。

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

轉(zhuǎn)換成二叉樹(shù)之后，需要讓這個(gè)無(wú)序堆變成最大堆，也就是每個(gè)堆都實(shí)現(xiàn)父節(jié)點(diǎn)的值大于任何一個(gè)子節(jié)點(diǎn)值。從最后一個(gè)堆開(kāi)始，依次比較父節(jié)點(diǎn)和子節(jié)點(diǎn)的值，如果子節(jié)點(diǎn)值大于父節(jié)點(diǎn)值，就需要交換。

創(chuàng)建最大堆： 6為最后一個(gè)子節(jié)點(diǎn)，所以從6開(kāi)始依次和父節(jié)點(diǎn)比較，如果子節(jié)點(diǎn)大于父節(jié)點(diǎn)，就需要交換子節(jié)點(diǎn)和父節(jié)點(diǎn)的位置。從設(shè)備樹(shù)圖形中可以看出，子節(jié)點(diǎn)6大于父節(jié)點(diǎn)4，所以需要交換子節(jié)點(diǎn)的父節(jié)點(diǎn)的位置。

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

交換 6 和4

6交換完成后，接下來(lái)依次向前比較其他子節(jié)點(diǎn)，6前面的節(jié)點(diǎn)是2，2小于父節(jié)點(diǎn)5，繼續(xù)向前查找子節(jié)點(diǎn)9，子節(jié)點(diǎn)9大于父節(jié)點(diǎn)5，所以就交換9和5的位置。

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

交換9和5

接下來(lái)繼續(xù)向前查找，發(fā)現(xiàn)子節(jié)點(diǎn)7大于父節(jié)點(diǎn)1，繼續(xù)交換。

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

交換7和1

繼續(xù)向前查找發(fā)現(xiàn)子節(jié)點(diǎn)9大于父節(jié)點(diǎn)8，交換位置。

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

交換9和8

繼續(xù)比較其他節(jié)點(diǎn)

公式：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

此時(shí)最大堆已經(jīng)創(chuàng)建完成，此時(shí)根節(jié)點(diǎn)的數(shù)字9就是數(shù)組中的最大值。

代碼中打印出來(lái)的數(shù)據(jù)順序和通過(guò)二叉樹(shù)圖形分析出來(lái)的順序完全一樣。此時(shí)最大堆調(diào)整已經(jīng)完成了。接下來(lái)就需要開(kāi)始堆排序，依次將根節(jié)點(diǎn)的數(shù)據(jù)存放到最后一個(gè)節(jié)點(diǎn)，形成一個(gè)有序堆。

堆排序（最大堆調(diào)整）

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

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

交換9和4

交換完成后，此時(shí)最大值9所在的底部位置就成為了有序區(qū)，有序區(qū)之后就不會(huì)參與任何對(duì)比。接下來(lái)繼續(xù)調(diào)整父節(jié)點(diǎn)和子節(jié)點(diǎn)，確保父節(jié)點(diǎn)要大于子節(jié)點(diǎn)。

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

交換8和4

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

交換6和4

此時(shí)數(shù)字8稱(chēng)為了根節(jié)點(diǎn)，是目前無(wú)序區(qū)中的最大值，將8和底部區(qū)的2交換，將當(dāng)前最大值8放到有序區(qū)中。

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

交換8和2

此時(shí)8已經(jīng)存放到了有序區(qū)中，此后就不參與任何交換了。此時(shí)2變?yōu)楦?jié)點(diǎn)后，需要在重新調(diào)整一次節(jié)點(diǎn)，確保父節(jié)點(diǎn)大于子節(jié)點(diǎn)。

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

交換7和2

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

交換3和2

此時(shí)數(shù)字7變?yōu)楦?jié)點(diǎn)，是無(wú)序區(qū)間的最大值。需要將根節(jié)點(diǎn)的數(shù)字移動(dòng)到有序區(qū)中。

將根節(jié)點(diǎn)7和0交換位置。

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

交換7和0

接下來(lái)重新調(diào)整節(jié)點(diǎn) 公式：6［0 ［5 7［8］］［4［9］］］ ［3［2］ ［1 ］］］

交換6和0

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

交換5和0

此時(shí)6變?yōu)榱烁?jié)點(diǎn)，是無(wú)序區(qū)間的最大值。

將根節(jié)點(diǎn)和有序區(qū)間的前一個(gè)數(shù)字交換，也就是1和6需要交換。

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

交換6和1

接下來(lái)重新調(diào)節(jié)一次節(jié)點(diǎn)

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

交換5和1

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

交換4和1

此時(shí)5變成的根節(jié)點(diǎn)，需要將5移動(dòng)到有序隊(duì)列中去。

接下來(lái)需要交換根節(jié)點(diǎn)5和無(wú)序節(jié)點(diǎn)2的位置

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

交換5和2

重新調(diào)整節(jié)點(diǎn)位置

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

交換4和2

此時(shí)4是無(wú)序列表中的最大值，需要交換4和1的位置

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

交換4和1

重新調(diào)整節(jié)點(diǎn)位置

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

交換3和1

此時(shí)3為無(wú)序列表中最大值，需要交換3和0的位置。

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

交換3和0

交換完成后重新調(diào)整節(jié)點(diǎn)位置 公式：9［0 ［2 6［7］］［3［8］］］ ［1［4］ ［5 ］］］

交換2和0

此時(shí)2變成了無(wú)序列表中最大值，1為有序列表的前一個(gè)值，交換2和1的位置。

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

交換2和1

此時(shí)1是根節(jié)點(diǎn)，無(wú)序列表中就剩0一個(gè)數(shù)字了，交換1和0。

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

交換1和0

這是0變成了根節(jié)點(diǎn)，而其他的所有數(shù)字都在有序列表中，無(wú)序列表中已經(jīng)沒(méi)有數(shù)字了，此時(shí)說(shuō)明排序完成。

可以看出最好、最壞、一般情況下數(shù)據(jù)移動(dòng)的次數(shù)和方法基本都差不多。

接下來(lái)隨機(jī)生成10000個(gè)數(shù)據(jù)，看看排序需要多長(zhǎng)時(shí)間。

編輯：jq