前幾天搞單片機(jī)，想要用到一個(gè)空間復(fù)雜度小點(diǎn)的排序算法。找到了堆排序和希爾排序。發(fā)現(xiàn)我算法幾乎都忘得差不多了...這里就復(fù)習(xí)記錄一下堆相關(guān)的東西吧。

堆是什么？

堆是一種完全二叉樹(shù)。

按照我的理解，如果一棵二叉樹(shù)從右往左、從下往上數(shù)的時(shí)候中間沒(méi)有斷檔，那這個(gè)二叉樹(shù)就算是完全二叉樹(shù)（嚴(yán)謹(jǐn)?shù)亩x自行百度）。像這樣的二叉樹(shù)就可以很方便地用數(shù)組表示。

其中每一個(gè)非葉節(jié)點(diǎn)和其子節(jié)點(diǎn)相比，處在一種排序方式里最靠前的位置。

大家給最常見(jiàn)的比大小的堆取了特殊的名字：從小到大的叫最小堆；從大到小的叫最大堆。

這樣的結(jié)構(gòu)有一個(gè)好處，堆的根節(jié)點(diǎn)的值一定是所有節(jié)點(diǎn)中最靠前的。接下來(lái)的堆排序和優(yōu)先隊(duì)列都是利用的這個(gè)性質(zhì)。

完全二叉樹(shù)的一些性質(zhì)

一般可以直接用數(shù)組來(lái)表示完全二叉樹(shù)，這里用一個(gè)長(zhǎng)度為6的數(shù)組舉例。

可以看到，最后一個(gè)非葉節(jié)點(diǎn)的下標(biāo)是2，即。

如果長(zhǎng)度變成7，因?yàn)檎?，結(jié)果還是2。

但長(zhǎng)度變?yōu)?后，2變?yōu)槿~節(jié)點(diǎn)。得到最后一個(gè)葉節(jié)點(diǎn)是1，公式和實(shí)際情況符合（這就不證明了）。

所以說(shuō)，如果一個(gè)用數(shù)組表示的完全二叉樹(shù)長(zhǎng)度是，那么其最后一個(gè)非葉節(jié)點(diǎn)的下標(biāo)為：

也就是說(shuō)，非葉節(jié)點(diǎn)下標(biāo)的范圍是?？梢杂眠@個(gè)范圍來(lái)判斷一個(gè)節(jié)點(diǎn)是否是非葉節(jié)點(diǎn)。

再看非葉節(jié)點(diǎn)和子節(jié)點(diǎn)的關(guān)系。

不難看出第個(gè)非葉節(jié)點(diǎn)的左子節(jié)點(diǎn)的下標(biāo)和右子節(jié)點(diǎn)的下標(biāo)為：

由這個(gè)性質(zhì)可以快速求出各個(gè)節(jié)點(diǎn)。

由構(gòu)造堆到堆排序

堆排序的核心思路是首先把序列轉(zhuǎn)化為堆，然后不斷取出根節(jié)點(diǎn)的值并維持剩余部分的堆結(jié)構(gòu)。最后把取出的值依次排列，就是一個(gè)有序的序列了。

要怎么轉(zhuǎn)化并維持一個(gè)堆呢？以最大堆為例，先從最簡(jiǎn)單的情況開(kāi)始。如果只有一個(gè)非葉節(jié)點(diǎn)，也就是只有兩個(gè)或三個(gè)節(jié)點(diǎn)的情況。那么要做的是選出它們中的最大值，如果最大值不是那個(gè)非葉節(jié)點(diǎn)，則將非葉節(jié)點(diǎn)的值和最大值互換。

由此這個(gè)互換操作可以擴(kuò)展到一般情況：

1. 如果被換的子節(jié)點(diǎn)是非葉節(jié)點(diǎn)，那么在經(jīng)過(guò)“互換”后被換的子樹(shù)可能不再是堆，需要對(duì)其再做一次“互換”。

2. 如果被換的子節(jié)點(diǎn)是葉節(jié)點(diǎn)，那么就沒(méi)有東西可換，直接結(jié)束。

3. 如果頂端本身就是最大，就不用再“互換”了，可以直接結(jié)束。

這種“互換”似乎被叫做heapify（堆化？）[1]那么后面就叫它堆化好了。根據(jù)上文的邏輯可以寫出堆化的實(shí)現(xiàn)（以最大堆為例）：

當(dāng)然也可以改成迭代版本，一般編譯器應(yīng)該是不會(huì)優(yōu)化尾遞歸的，可以少占點(diǎn)內(nèi)存：

實(shí)現(xiàn)了互換之后，就可以把一個(gè)數(shù)組構(gòu)造成最大堆了。將所有非葉節(jié)點(diǎn)由下往上堆化，即可構(gòu)造出堆?？梢韵胂笠幌掳汛髷?shù)往上浮的這么個(gè)過(guò)程，讓我聯(lián)想到了晉級(jí)賽，或者說(shuō)二維情況下的冒泡。下面是實(shí)現(xiàn)：

最后是堆排序的實(shí)現(xiàn)。實(shí)現(xiàn)的思路和選擇排序類似，分成了兩個(gè)區(qū)域，已排序區(qū)域和未排序區(qū)域。每次都把根節(jié)點(diǎn)的值和最后一個(gè)節(jié)點(diǎn)交換位置，然后把末尾變?yōu)橐雅判騾^(qū)，最終得到的就是一個(gè)有序的序列了（這里是從小到大）。

最后順便提一下優(yōu)先隊(duì)列

可能看完堆排序后，大家心里應(yīng)該就由優(yōu)先隊(duì)列的雛形了。沒(méi)錯(cuò)關(guān)鍵點(diǎn)還是這個(gè)堆化heapify。

新節(jié)點(diǎn)入隊(duì)后，遞歸地對(duì)其上層節(jié)點(diǎn)做heapify就可以維持優(yōu)先。節(jié)點(diǎn)的上層節(jié)點(diǎn)為

因此實(shí)現(xiàn)代碼類似于

至于出隊(duì)，這個(gè)和堆排序中每一步迭代的操作是一致的，就不重復(fù)了。

一些參考

阿B不讓貼站外鏈，那就只能貼一個(gè)了。