本節(jié)介紹第二種選擇排序：堆排序。

堆排序定義

n 個(gè)關(guān)鍵字序列 K1，K2，…，Kn 稱為堆，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)(簡(jiǎn)稱為堆性質(zhì))：

http://wiki.jikexueyuan.com/project/data-structure-sorting/images/dss.jpg" alt="" />

若將此序列所存儲(chǔ)的向量 R[1..n]看做是一棵完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹(shù)：樹(shù)中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的關(guān)鍵字。

【例】關(guān)鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(zhì)(1)和(2)，故它們均是堆，其對(duì)應(yīng)的完全二叉樹(shù)分別如小根堆示例和大根堆示例所示。

http://wiki.jikexueyuan.com/project/data-structure-sorting/images/dss1.jpg" alt="" />

大根堆和小根堆

根結(jié)點(diǎn)(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最小者的堆稱為小根堆。

根結(jié)點(diǎn)(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大者，稱為大根堆。

注意：

• 堆中任一子樹(shù)亦是堆。
• 以上討論的堆實(shí)際上是二叉堆(Binary Heap)，類似地可定義k叉堆。

堆排序特點(diǎn)

堆排序(HeapSort)是一樹(shù)形選擇排序。

堆排序的特點(diǎn)是：在排序過(guò)程中，將 R[l..n]看成是一棵完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹(shù)中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系【參見(jiàn)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)】，在當(dāng)前無(wú)序區(qū)中選擇關(guān)鍵字最大(或最小)的記錄。

堆排序與直接插入排序的區(qū)別

直接選擇排序中，為了從 R[1..n]中選出關(guān)鍵字最小的記錄，必須進(jìn)行 n-1 次比較，然后在 R[2..n]中選出關(guān)鍵字最小的記錄，又需要做 n-2 次比較。事實(shí)上，后面的 n-2 次比較中，有許多比較可能在前面的 n-1 次比較中已經(jīng)做過(guò)，但由于前一趟排序時(shí)未保留這些比較結(jié)果，所以后一趟排序時(shí)又重復(fù)執(zhí)行了這些比較操作。堆排序可通過(guò)樹(shù)形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)。

堆排序

堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征，使得在當(dāng)前無(wú)序區(qū)中選取最大(或最小)關(guān)鍵字的記錄變得簡(jiǎn)單。

（1）用大根堆排序的基本思想

• 先將初始文件 R[1..n]建成一個(gè)大根堆，此堆為初始的無(wú)序區(qū)
• 再將關(guān)鍵字最大的記錄 R[1]即堆頂和無(wú)序區(qū)的最后一個(gè)記錄 R[n]交換，由此得到新的無(wú)序區(qū) R[1..n-1]和有序區(qū) R[n]，且滿足 R[1..n-1].keys≤R[n].key
• 由于交換后新的根 R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無(wú)序區(qū) R[1..n-1]調(diào)整為堆。然后再次將 R[1..n-1]中關(guān)鍵字最大的記錄 R[1]和該區(qū)間的最后一個(gè)記錄 R[n-1]交換，由此得到新的無(wú)序區(qū) R[1..n-2]和有序區(qū) R[n-1..n]，且仍滿足關(guān)系 R[1..n-2].keys≤R[n-1..n].keys，同樣要將 R[1..n-2]調(diào)整為堆?！钡綗o(wú)序區(qū)只有一個(gè)元素為止。

（2）大根堆排序算法的基本操作：

• 初始化操作：將 R[1..n]構(gòu)造為初始堆；
• 每一趟排序的基本操作：將當(dāng)前無(wú)序區(qū)的堆頂記錄 R[1] 和該區(qū)間的最后一個(gè)記錄交換，然后將新的無(wú)序區(qū)調(diào)整為堆(亦稱重建堆)。

注意：

• 只需做 n-1 趟排序，選出較大的 n-1 個(gè)關(guān)鍵字即可以使得文件遞增有序。
• 用小根堆排序與利用大根堆類似，只不過(guò)其排序結(jié)果是遞減有序的。堆排序和直接選擇排序相反：在任何時(shí)刻，堆排序中無(wú)序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴(kuò)大至整個(gè)向量為止。

（3）堆排序的算法：

void HeapSort(SeqIAst R)  
 { //對(duì)R[1..n]進(jìn)行堆排序，不妨用R[0]做暫存單元  
  int i；  
  BuildHeap(R)； //將R[1-n]建成初始堆  
  for(i=n;i>1；i--){ //對(duì)當(dāng)前無(wú)序區(qū)R[1..i]進(jìn)行堆排序，共做n-1趟。  
    R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //將堆頂和堆中最后一個(gè)記錄交換  
   Heapify(R，1，i-1)； //將R[1..i-1]重新調(diào)整為堆，僅有R[1]可能違反堆性質(zhì)  
   } //endfor  
 } //HeapSort 

(4) BuildHeap 和 Heapify 函數(shù)的實(shí)現(xiàn)

因?yàn)闃?gòu)造初始堆必須使用到調(diào)整堆的操作，先討論 Heapify 的實(shí)現(xiàn)。

Heapify 函數(shù)思想方法

每趟排序開(kāi)始前 R[l..i]是以 R[1]為根的堆，在 R[1]與 R[i]交換后，新的無(wú)序區(qū) R[1..i-1]中只有 R[1]的值發(fā)生了變化，故除 R[1]可能違反堆性質(zhì)外，其余任何結(jié)點(diǎn)為根的子樹(shù)均是堆。因此，當(dāng)被調(diào)整區(qū)間是 R[low..high]時(shí)，只須調(diào)整以 R[low]為根的樹(shù)即可。

"篩選法"調(diào)整堆

R[low]的左、右子樹(shù)(若存在)均已是堆，這兩棵子樹(shù)的根 R[2low]和 R[2low+1]分別是各自子樹(shù)中關(guān)鍵字最大的結(jié)點(diǎn)。若 R[low].key不小于這兩個(gè)孩子結(jié)點(diǎn)的關(guān)鍵字，則 R[low]未違反堆性質(zhì)，以 R[low]為根的樹(shù)已是堆，無(wú)須調(diào)整；否則必須將 R[low]和它的兩個(gè)孩子結(jié)點(diǎn)中關(guān)鍵字較大者進(jìn)行交換，即 R[low]與 R[large](R[large].key=max(R[2low].key，R[2low+1].key))交換。交換后又可能使結(jié)點(diǎn) R[large]違反堆性質(zhì)，同樣由于該結(jié)點(diǎn)的兩棵子樹(shù)(若存在)仍然是堆，故可重復(fù)上述的調(diào)整過(guò)程，對(duì)以 R[large]為根的樹(shù)進(jìn)行調(diào)整。此過(guò)程直至當(dāng)前被調(diào)整的結(jié)點(diǎn)已滿足堆性質(zhì)，或者該結(jié)點(diǎn)已是葉子為止。上述過(guò)程就象過(guò)篩子一樣，把較小的關(guān)鍵字逐層篩下去，而將較大的關(guān)鍵字逐層選上來(lái)。因此，有人將此方法稱為"篩選法"。

BuildHeap 的實(shí)現(xiàn)

要將初始文件 R[l..n]調(diào)整為一個(gè)大根堆，就必須將它所對(duì)應(yīng)的完全二叉樹(shù)中以每一結(jié)點(diǎn)為根的子樹(shù)都調(diào)整為堆。 顯然只有一個(gè)結(jié)點(diǎn)的樹(shù)是堆，而在完全二叉樹(shù)中，所有序號(hào)http://wiki.jikexueyuan.com/project/data-structure-sorting/images/i.gif" alt="" />的結(jié)點(diǎn)都是葉子，因此以這些結(jié)點(diǎn)為根的子樹(shù)均已是堆。這樣，我們只需依次將以序號(hào)為http://wiki.jikexueyuan.com/project/data-structure-sorting/images/i1.gif" alt="" /> ，http://wiki.jikexueyuan.com/project/data-structure-sorting/images/i1.gif" alt="" /> -1，…，1的結(jié)點(diǎn)作為根的子樹(shù)都調(diào)整為堆即可。

大根堆排序?qū)嵗?/h2>

對(duì)于關(guān)鍵字序列(42，13，24，91，23，16，05，88)，在建堆過(guò)程中完全二叉樹(shù)及其存儲(chǔ)結(jié)構(gòu)的變化情況參見(jiàn)【動(dòng)畫(huà)演示】。

算法分析

堆排序的時(shí)間，主要由建立初始堆和反復(fù)重建堆這兩部分的時(shí)間開(kāi)銷構(gòu)成，它們均是通過(guò)調(diào)用 Heapify 實(shí)現(xiàn)的。

堆排序的最壞時(shí)間復(fù)雜度為 O(nlgn)。堆排序的平均性能較接近于最壞性能。

由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。

堆排序是就地排序，輔助空間為 O(1)，它是不穩(wěn)定的排序方法。