完全二叉樹可以和數(shù)組完美轉(zhuǎn)換
若將完全二叉樹的節(jié)點按構(gòu)件順序進行編號（從0開始，即樹根節(jié)點編號為0）腌逢。
性質(zhì)1：節(jié)點i的兩個子節(jié)點的編號為2i+1和2i+2.
性質(zhì)2：由性質(zhì)1可得，當(dāng)i > 0 時，其父節(jié)點為 floor((i-1)/2)
性質(zhì)3：完全二叉樹中最后一個有子節(jié)點的節(jié)點為 n/2 - 1。 n為節(jié)點數(shù)量
利用頂堆的堆積排序：
大/小頂堆的性質(zhì)：
1霞扬、頂堆一定是完全二叉樹，所以可以用數(shù)組直接表示
2枫振、大/小頂堆的每個子樹也是大/小頂堆
排序思路：
基本思想：把待排序的元素按照大小在二叉樹位置上排列喻圃，排序好的元素要滿足：父節(jié)點的元素要大于等于其子節(jié)點；這個過程叫做堆化過程粪滤，如果根節(jié)點存放的是最大的數(shù)斧拍，則叫做大根堆；如果是最小的數(shù)杖小，自然就叫做小根堆了肆汹。根據(jù)這個特性（大根堆根最大，小根堆根最杏枞ā）昂勉，就可以把根節(jié)點拿出來，然后再堆化下扫腺，再把根節(jié)點拿出來岗照，闪湾，凰棉，集漾，循環(huán)到最后一個節(jié)點症见，就排序好了。
參考1：https://blog.csdn.net/YuZhiHui_No1/article/details/44258297
參考2：http://www.seotest.cn/jishu/46956.html
實現(xiàn)：
1舶赔、堆化過程：從最后一個分支結(jié)點（n div 2）開始臼朗，到根（1）為止胸蛛，依次對每個分支結(jié)點進行調(diào)整（下沉）习绢，以便形成以每個分支結(jié)點為根的堆，當(dāng)最后對樹根結(jié)點進行調(diào)整后，整個樹就變成了一個堆闪萄。
所謂下沉梧却，即將節(jié)點通過不斷與自己的子節(jié)點進行比較、交換败去，直到行進到某個位置使得自己是當(dāng)前子樹中最大或最小的放航。因為單獨的下沉過程并不能保證子樹的正確性。所以一定要從最下層有子節(jié)點的節(jié)點開始下沉圆裕，以保證整體算法的正確性广鳍。
2、方法是依次將堆的根節(jié)點數(shù)記下吓妆，然后刪除根節(jié)點赊时，如此反復(fù)直到堆為空。上面提到了刪除操作行拢，每次刪除之后都是要調(diào)整堆讓堆的性質(zhì)不變祖秒，即根節(jié)點必為最大值或最小值。
具體操作可以使每次都將根節(jié)點與當(dāng)前排序的數(shù)組片段的最后一位互換舟奠，然后對新數(shù)組的第一個元素進行下沉操作（并將進行堆化的數(shù)組長度-1）
由頂堆的性質(zhì)（或根據(jù)堆化的過程）可知竭缝，在排序階段，除每次的頂點外的其他頂點都是已經(jīng)經(jīng)過下沉操作的沼瘫，所以直接對新頂點進行下沉即可得到新的頂堆
#include "core.hpp"
void heap(int *data, int size);
void ad_heap(int *data, int i, int size);
void heap(int *data, int size){
// int i, j, tmp;
// 根據(jù)性質(zhì)可得抬纸，節(jié)點 i = size/2 -1 是最后一個有子節(jié)點的節(jié)點
// 且i節(jié)點之前的所有節(jié)點都一定有兩個子樹
// 從節(jié)點i開始向前，對所有節(jié)點進行下沉操作耿戚，保證當(dāng)前節(jié)點下的所有子樹的正確性
for(int i=(size/2 - 1);i>=0;i--){
ad_heap(data, i, size);
}
cout << "\n 堆積內(nèi)容：";
print_array(data, size);
for(int i = size - 2; i >0; i--){
mswap(data[0], data[i+1]); // 交換堆化后數(shù)組的第一個值和最后一個值湿故， mswap僅實現(xiàn)了數(shù)值交換
ad_heap(data,0, i); // 對長度減一的數(shù)組的根節(jié)點進行下沉操作
}
print_array(data, size);
}
// 該函數(shù)的作用是將節(jié)點i的值下沉到正確位置，并不是將以i為頂點的二叉樹轉(zhuǎn)為頂堆
// 當(dāng)下沉到某個節(jié)點溅话，使得i的值比當(dāng)前節(jié)點兩個子節(jié)點斗大即完成下沉
// 子樹的正確性由調(diào)用函數(shù)保證
void ad_heap(int *data, int i, int size){
cout << "called====================" << endl;
int j, tmp, post;
j = 2*i + 1;
tmp = data[i];
post = 0;
while (j < size && post ==0){
cout << "j: " << j << " i: " << i << " root: " << tmp << " left: " << data[j] << endl;
if(j < size && j+1 < size){ // 標(biāo)記左右子樹中最大的一個
if(data[j] < data[j+1]){
j++;
}
}
if(tmp >= data[j]){ // 如果當(dāng)前節(jié)點比左右子樹都大則認(rèn)為下沉完成
post = 1; // 不再進一步校驗下一層的原因是晓锻，默認(rèn)子樹已經(jīng)完成下沉，再進行校驗就是重復(fù)校驗了
}
else{
data[(j-1)/2] = data[j]; // 當(dāng)前節(jié)點小于左節(jié)點或右節(jié)點飞几，需要交換該子節(jié)點的值與當(dāng)前根節(jié)點的值
j = 2*j + 1; // 因為發(fā)生了交換砚哆，不能保證交換后的各個子樹仍然正確，故需要繼續(xù)對下一層進行檢查
}
}
data[(j-1)/2] = tmp;
print_array(data, size);
cout << "end====================" << endl;
}
int main(){
int data[8] = {34,19,40,14,57,17,4,43};
heap(data, 8);
return 0;
}
