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

（1）用大根堆排序的基本思想
①先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區(qū)
②再將關(guān)鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key
③由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(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)整為堆。
……
直到無序區(qū)只有一個元素為止。

（2）大根堆排序算法的基本操作：
① 初始化操作：將R[1..n]構(gòu)造為初始堆；
②每一趟排序的基本操作：將當前無序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個記錄交換，然后將新的無序區(qū)調(diào)整為堆(亦稱重建堆)。
注意：
①只需做n-1趟排序，選出較大的n-1個關(guān)鍵字即可以使得文件遞增有序。
②用小根堆排序與利用大根堆類似，只不過其排序結(jié)果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻，堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴大至整個向量為止。

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

（4）BuildHeap和Heapify函數(shù)的實現(xiàn)
　因為構(gòu)造初始堆必須使用到調(diào)整堆的操作，先討論Heapify的實現(xiàn)。
① Heapify函數(shù)思想方法
　每趟排序開始前R[l..i]是以R[1]為根的堆，在R[1]與R[i]交換后，新的無序區(qū)R[1..i-1]中只有R[1]的值發(fā)生了變化，故除R[1]可能違反堆性質(zhì)外，其余任何結(jié)點為根的子樹均是堆。因此，當被調(diào)整區(qū)間是R[low..high]時，只須調(diào)整以R[low]為根的樹即可。
"篩選法"調(diào)整堆
　R[low]的左、右子樹(若存在)均已是堆，這兩棵子樹的根R[2low]和R[2low+1]分別是各自子樹中關(guān)鍵字最大的結(jié)點。若R[low].key不小于這兩個孩子結(jié)點的關(guān)鍵字，則R[low]未違反堆性質(zhì)，以R[low]為根的樹已是堆，無須調(diào)整；否則必須將R[low]和它的兩個孩子結(jié)點中關(guān)鍵字較大者進行交換，即R[low]與R[large](R[large].key=max(R[2low].key，R[2low+1].key))交換。交換后又可能使結(jié)點R[large]違反堆性質(zhì)，同樣由于該結(jié)點的兩棵子樹(若存在)仍然是堆，故可重復(fù)上述的調(diào)整過程，對以R[large]為根的樹進行調(diào)整。此過程直至當前被調(diào)整的結(jié)點已滿足堆性質(zhì)，或者該結(jié)點已是葉子為止。上述過程就象過篩子一樣，把較小的關(guān)鍵字逐層篩下去，而將較大的關(guān)鍵字逐層選上來。因此，有人將此方法稱為"篩選法"。

②BuildHeap的實現(xiàn)
　　要將初始文件R[l..n]調(diào)整為一個大根堆，就必須將它所對應(yīng)的完全二叉樹中以每一結(jié)點為根的子樹都調(diào)整為堆。
　　顯然只有一個結(jié)點的樹是堆，而在完全二叉樹中，所有序號 的結(jié)點都是葉子，因此以這些結(jié)點為根的子樹均已是堆。這樣，我們只需依次將以序號為 ， -1，…，1的結(jié)點作為根的子樹都調(diào)整為堆即可。