1、 堆排序定義
    　n個關鍵字序列Kl，K2，…，Kn稱為堆，當且僅當該序列滿足如下性質(簡稱為堆性質)：
    　(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤  )

    　若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大于(或不小于)其左右孩子(若存在)結點的關鍵字。
【例】關鍵字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分別滿足堆性質(1)和(2)

2、大根堆和小根堆
    　根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆。
    　根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆。
  注意：
    　①堆中任一子樹亦是堆。
   　 ②以上討論的堆實際上是二叉堆(Binary Heap)，類似地可定義k叉堆。

3、堆排序特點
    　堆排序(HeapSort)是一樹形選擇排序。
    　堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系【參見二叉樹的順序存儲結構】，在當前無序區(qū)中選擇關鍵字最大(或最小)的記錄。

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

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

（1）用大根堆排序的基本思想
① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區(qū)
② 再將關鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key
③ 由于交換后新的根R[1]可能違反堆性質，故應將當前無序區(qū)R[1..n-1]調整為堆。然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區(qū) 間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R [n-1..n].keys，同樣要將R[1..n-2]調整為堆。
    ……
直到無序區(qū)只有一個元素為止。

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

（3）堆排序的算法：
  void HeapSort(SeqIAst R)
   { //對R[1..n]進行堆排序，不妨用R[0]做暫存單元
    int i；
    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]重新調整為堆，僅有R[1]可能違反堆性質
     } //endfor
   } //HeapSort

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

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

5、大頂堆排序實現(xiàn)

void HeapSort ( Elem R[], int n ) ...{
// 對記錄序列R[1..n]進行堆排序。
for ( i=n/2; i>0; --i )
                    // 把R[1..n]建成大頂堆
   HeapAdjust ( R, i, n );
for ( i=n; i>1; --i ) ...{
R[1]←→R;         
        // 將堆頂記錄和當前未經(jīng)排序子序列
        // R[1..i]中最后一個記錄相互交換
HeapAdjust(R, 1, i-1);           
        // 將R[1..i-1] 重新調整為大頂堆
}
} // HeapSort
其中篩選的算法如下所示。為將R[s..m]調整為“大頂堆”，算法中“篩選”應沿關鍵字較大的孩子結點向下進行。
void HeapAdjust (Elem R[], int s, int m) ...{
// 已知R[s..m]中記錄的關鍵字除R[s].key之
// 外均滿足堆的定義，本函數(shù)調整R[s] 的關
// 鍵字，使R[s..m]成為一個大頂堆（對其中
// 記錄的關鍵字而言）
rc = R[s];
for ( j=2*s; j<=m; j*=2 ) ...{// 沿key較大的孩子結點向下篩選
    if ( j<m && R[j].key<R[j+1].key)  ++j;
    if ( rc.key >= R[j].key )  break; // rc應插入在位置s上
    R[s] = R[j];  s = j;
}
    R[s] = rc; // 插入
} // HeapAdjust

6、 算法分析
    　堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現(xiàn)的。
  　  堆排序的最壞時間復雜度為O(nlgn)。堆排序的平均性能較接近于最壞性能。
    　由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。
    　堆排序是就地排序，輔助空間為O(1)，
    　它是不穩(wěn)定的排序方法。