1.堆
堆實際上是一棵完全二叉樹，其任何一非葉節點滿足性質：
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]
即任何一非葉節點的關鍵字不大于或者不小于其左右孩子節點的關鍵字。
堆分為大頂堆和小頂堆，滿足Key[i]>=Key[2i+1]&&key>=key[2i+2]稱為大頂堆，滿足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]稱為小頂堆。由上述性質可知大頂堆的堆頂的關鍵字肯定是所有關鍵字中最大的，小頂堆的堆頂的關鍵字是所有關鍵字中最小的。
2.堆排序的思想
利用大頂堆(小頂堆)堆頂記錄的是最大關鍵字(最小關鍵字)這一特性，使得每次從無序中選擇最大記錄(最小記錄)變得簡單。
其基本思想為(大頂堆)：
1)將初始待排序關鍵字序列(R1,R2....Rn)構建成大頂堆，此堆為初始的無序區；
2)將堆頂元素R[1]與最后一個元素R[n]交換，此時得到新的無序區(R1,R2,......Rn-1)和新的有序區(Rn),且滿足R[1,2...n-1]<=R[n];
3)由于交換后新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1,R2,......Rn-1)調整為新堆，然后再次將R[1]與無序區最后一個元素交換，得到 新的無序區(R1,R2....Rn-2)和新的有序區(Rn-1,Rn)。不斷重復此過程直到有序區的元素個數為n-1，則整個排序過程完成。
3.操作過程如下：
1)初始化堆：將R[1..n]構造為堆；
2)將當前無序區的堆頂元素R[1]同該區間的最后一個記錄交換，然后將新的無序區調整為新的堆。
因此對于堆排序，最重要的兩個操作就是構造初始堆和調整堆，其實構造初始堆事實上也是調整堆的過程，只不過構造初始堆是對所有的非葉節點都進行調整。
4.舉例說明堆排序的操作過程
a首先是講一個無序的序列構建成一個個堆：
?
?b.然后是輸出堆頂元素之后，調整剩余元素成為一個新的堆：
5.下面是代碼部分：
#include<iostream> #include<cstring> #include<string> #include<queue> #include<map> #include<cstdlib> #include<cstdio> const int INF=0X3f3f3f3f; using namespace std;typedef struct {int a[100];int len;void outList(){for(int i=1; i<=len; ++i)cout<<a[i]<<" ";cout<<endl;} }list; list L; /**********************************************************************************/void heapAdjust(int ld, int rd){//堆排序, 排序區間[ld，rd] int rc = L.a[ld];int cur = ld;for(int p = ld*2; p<=rd; p=p*2){if(p<rd && L.a[p] > L.a[p+1]) ++p;//取左右子樹的最小值if(rc < L.a[p]) break;//如果父節點的值比左右子樹的值都小，那么已經調整好了，已經是小堆頂了L.a[cur] = L.a[p];//否則交換父節點和左右子樹最小的子樹的值，父節點的值存在rc中，所以只要將最小子樹的值賦給父節點就好 cur = p;}L.a[cur] = rc; }/**********************************************************************************/int main() {int i;scanf("%d", &L.len);for(i=1; i<=L.len; i++)scanf("%d", &L.a[i]);for(int i=L.len/2; i>=1; --i)//將整個區間調整成小堆頂，從最后一個非終結點開始 heapAdjust(i, L.len);for(int i=1; i<=L.len; ++i) {cout<<L.a[1]<<" "; L.a[1] = L.a[L.len-i+1];//將最后一個元素賦給第一個元素 heapAdjust(1, L.len-i);//重新調整堆 }cout<<endl;return 0; }
?
)
)
