二叉堆（Binary Heap）是一顆特殊的完全二叉樹，一般分為大頂堆和小頂堆，我就不啰嗦啦！具體內(nèi)容你可以看一下 圖解：什么是二叉堆？

堆排序

要學(xué)習(xí)今天的堆排序（Heap Sort），我們以一個數(shù)組  arr = [5、1、4、2、8、4] 開始（這個數(shù)組我們之前講排序算法常用的）：

我們首先以這個數(shù)組建立一個大頂堆，插入結(jié)點(diǎn) 5 作為根結(jié)點(diǎn)：

然后將結(jié)點(diǎn) 1 插入到最后一個位置，也就是結(jié)點(diǎn) 5 的左孩子，1 < 5 ，滿足大頂堆的屬性：

將結(jié)點(diǎn) 4 插入到最后一個位置，即結(jié)點(diǎn) 5 的右孩子 ，又因?yàn)?4 < 5 ，滿足大頂堆的屬性，不需要進(jìn)行調(diào)整：

將結(jié)點(diǎn) 2 插入到最后一個位置，即結(jié)點(diǎn) 1 的左孩子位置，但是此時不滿足大頂堆的屬性（插入結(jié)點(diǎn) 2 小于其父結(jié)點(diǎn) 1 的值），所以交換兩者的值；此時并未結(jié)束，繼續(xù)判斷此時插入結(jié)點(diǎn) 2 與當(dāng)前父結(jié)點(diǎn) 5 的大小關(guān)系，發(fā)現(xiàn) 2 < 5 ，滿足大頂堆的屬性，結(jié)束判斷。這個過程就是二叉堆的插入操作：

緊接著將結(jié)點(diǎn) 8 插入到最后一個位置，即結(jié)點(diǎn) 2 的右孩子位置，此時不滿足大頂堆的屬性（插入結(jié)點(diǎn) 8 小于其父結(jié)點(diǎn) 2 ），故交換兩者位置；然后繼續(xù)向上修正，判斷當(dāng)前結(jié)點(diǎn) 8 與其父結(jié)點(diǎn) 5 的大小關(guān)系，8 > 5 （不滿足大頂堆的屬性），交換兩者位置，繼續(xù)修正，發(fā)現(xiàn)結(jié)點(diǎn) 8 已為樹的根結(jié)點(diǎn)，修正結(jié)束：

最后，我們將結(jié)點(diǎn) 4 插入到最后一個位置，即結(jié)點(diǎn) 4（下標(biāo)為2） 的左孩子位置，且其值小于等于父結(jié)點(diǎn)，故不進(jìn)行修正：

以上算是對于二叉堆插入操作的一個回顧，建堆的過程（這里是按照插入操作進(jìn)行建堆的），接下來才是堆排序的核心操作。

設(shè) 表示堆中的元素個數(shù)，對數(shù)組 arr = [8,5,4,1,2,4] 而言， ;

第一步：將堆頂?shù)脑?8 （即數(shù)組 arr[0] ，最大元素）的元素與堆的最后一個元素 4（即數(shù)組當(dāng)中的最后一個元素 4 ）交換，此時就相當(dāng)于選擇出了數(shù)組當(dāng)中的最大元素，將其從堆中去掉：

第二步：從結(jié)點(diǎn) 4 （下標(biāo)為 0 ）開始進(jìn)行 堆化（Heapify）操作，這里我們只啰嗦一次奧！計算結(jié)點(diǎn) 4 （下標(biāo)為 0 ）的左孩子 （即結(jié)點(diǎn) 5 ），右孩子 （即結(jié)點(diǎn) 4），比較三者的大小，發(fā)現(xiàn) 5 > 4 違反了堆的性質(zhì)，交換 5 和根結(jié)點(diǎn) 4 ；然后繼續(xù)對結(jié)點(diǎn) 4 （下標(biāo)為 1 ）進(jìn)行判斷，發(fā)現(xiàn)其左孩子 1 和右孩子 2 均小于 4 ，堆化結(jié)束。

第三步：將堆頂元素 5 （下標(biāo)為 0）和當(dāng)前最后一個元素 2 （即 i 指向的位置）交換， 此時就相當(dāng)于選擇出了數(shù)組當(dāng)中的次最大元素，將其從堆中去掉：

第四步：從當(dāng)前的堆頂元素 2 開始進(jìn)行堆化操作，交換 2 （下標(biāo) 0）和其左孩子 4 （下標(biāo) 1），為什么不是右孩子 4 （下標(biāo) 2）呢？因?yàn)槲覀冊诙鸦臅r候，優(yōu)先和左孩子進(jìn)行了對比，只有當(dāng)右孩子大于左孩子的情況下，才考慮將右孩子與其父結(jié)點(diǎn)交換，堆化后的結(jié)果如下圖所示：

第五步：交換根結(jié)點(diǎn) 4 和最后一個結(jié)點(diǎn) 1 ，從堆中去掉結(jié)點(diǎn) 4 （下標(biāo) 3）：

第六步：從根結(jié)點(diǎn) 1 開始進(jìn)行堆化操作，交換了根結(jié)點(diǎn) 1 和 4 （下標(biāo) 2）：

第七步：交換根結(jié)點(diǎn) 4 和 1 ，從堆中去掉結(jié)點(diǎn) 4 ：

第八步：從根結(jié)點(diǎn) 1 開始進(jìn)行堆化操作，交換了結(jié)點(diǎn) 2 和 1 ：

第九步：交換根結(jié)點(diǎn) 2 和最后一個元素 1 ，將結(jié)點(diǎn) 2 從堆中去掉：

第十步：發(fā)現(xiàn)堆中僅剩余一個元素，堆排序結(jié)束，我們看到原始的輸入數(shù)組   arr = [5、1、4、2、8、4]  變成了有序數(shù)組   arr = [1、2、4、4、5、8]  。

這就是有趣有好玩的堆排序，其本質(zhì)上是對二叉堆的一個應(yīng)用。

我們都知道選擇排序是利用線性的時間復(fù)雜度 遍歷數(shù)組，每一趟選擇出數(shù)組當(dāng)中最大的元素，總共選擇 趟，所以選擇排序的時間復(fù)雜度為 。

而堆排序事實(shí)上就是對選擇排序的一個優(yōu)化，本來用 的時間才能選擇出數(shù)組中最大或最小元素，借助于大頂堆和小頂堆數(shù)據(jù)結(jié)構(gòu)，就可以將這個選擇操作的時間復(fù)雜度降到 ，同樣是選擇 趟，所以堆排序的時間復(fù)雜度為 量級。

不難發(fā)現(xiàn)，堆排序是一個基于比較的排序算法，且在排序過程中由于要進(jìn)行堆化操作（不斷交換）（Heapify），而造成其不穩(wěn)定性，所以堆排序是一個不穩(wěn)定的排序算法。

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

只要會寫二叉堆的堆化操作，看堆排序的代碼會相當(dāng)簡單。

請注意：上面代碼中的建堆操作代碼

for (int i = n / 2 - 1; i >= 0; i--){
    heapify(arr, n, i); 
} 

如果看這個代碼感覺不舒服，沒關(guān)系，我們用更香的方式來一遍。我們還是以數(shù)組   arr = [5、1、4、2、8、4]  為例說明這種建堆方式。

與插入操作建堆不同的是（插入操作建堆將原數(shù)組當(dāng)做一個普通的數(shù)組），我們將數(shù)組 arr[] 從一開始就當(dāng)做一顆完全二叉樹：

然后計算 i = 6/2 - 1 = 2 ，對結(jié)點(diǎn) 4（2） 應(yīng)用堆化操作，發(fā)現(xiàn)大于等于其左孩子 4（5） 的值（其中括號中的數(shù)字表示下標(biāo)）：

i-- ，i = 1 ，對結(jié)點(diǎn) 1（1） 應(yīng)用堆化操作，計算其左孩子結(jié)點(diǎn) 2（3） ，右孩子結(jié)點(diǎn) 8（4） ，比較三者大小，發(fā)現(xiàn)結(jié)點(diǎn)  1（1） 的左右孩子均比其大，將最大結(jié)點(diǎn) 8（4） 和  1（1） 交換，此時   1（1） 已經(jīng)到葉子結(jié)點(diǎn)了：

i-- = 0 ，對結(jié)點(diǎn) 5（0） 應(yīng)用堆化操作，發(fā)現(xiàn)左孩子 8（3） 比其大，交換兩者，繼續(xù)對 5（3） 進(jìn)行堆化，發(fā)現(xiàn)左右孩子均比其小，堆化結(jié)束：

這樣我們就得到了一個大頂堆。

一個更有意思的問題來了，那你知道剛才講的 建堆時間復(fù)雜度是多少呢？

咋一看，這還不簡單，每次調(diào)用 Heapify() 函數(shù)的時間復(fù)雜度為 ，建堆調(diào)用了 次，所以剛才講的建堆操作的時間復(fù)雜度就是 量級。

雖然上面的建堆操作的時間復(fù)雜度的上限 量級沒有錯誤，但是這個復(fù)雜度不是漸近嚴(yán)格的。

Heapify() 函數(shù)的運(yùn)行時間取決于樹的高度 （ , 其中 n 是結(jié)點(diǎn)個數(shù)），而大多數(shù)子樹的高度是小于 的。

建堆的循環(huán)是從倒數(shù)第一層的結(jié)點(diǎn) 的位置開始的（其高度為1），一直遍歷到根結(jié)點(diǎn) 1 位置（高度為 ），因此，堆化（Heapify）對不同的結(jié)點(diǎn)的所耗費(fèi)的時間是不同的，只能暫時認(rèn)為堆化（Heapify）的運(yùn)行時間為 ，而這個 是變化的。

要想準(zhǔn)確計算出建堆的時間復(fù)雜度，就必須知道對于高度為 的頂點(diǎn)的個數(shù)是多少。

這里就要告訴大家一個不爭的事實(shí)啦，對于一個大小為 的堆而言，高度為 的頂點(diǎn)個數(shù)最多為 個。比如高度為 1（即 ）的結(jié)點(diǎn)的個數(shù)最多為 個。

那么建堆的時間復(fù)雜度就好算了，對于高度為 的結(jié)點(diǎn)的運(yùn)行時間為 ，而 的變化范圍為 0 到 ，計算累加和，即：

已知：

那么：

因此，建立一個二叉堆的時間復(fù)雜度為 量級。

證明建立一個二叉堆的時間復(fù)雜度對于學(xué)習(xí)堆排序似乎沒有特別的意義，但希望考研、學(xué)習(xí)高等數(shù)學(xué)的朋友看到數(shù)學(xué)的魅力，還有數(shù)據(jù)結(jié)構(gòu)的算法復(fù)雜度細(xì)究其實(shí)還是很有趣的。