完全二叉樹(shù)可以和數(shù)組完美轉(zhuǎn)換

若將完全二叉樹(shù)的節(jié)點(diǎn)按構(gòu)件順序進(jìn)行編號(hào)（從0開(kāi)始，即樹(shù)根節(jié)點(diǎn)編號(hào)為0）。

性質(zhì)1：節(jié)點(diǎn)i的兩個(gè)子節(jié)點(diǎn)的編號(hào)為2i+1和2i+2.

性質(zhì)2：由性質(zhì)1可得，當(dāng)i > 0 時(shí)，其父節(jié)點(diǎn)為 floor((i-1)/2)

性質(zhì)3：完全二叉樹(shù)中最后一個(gè)有子節(jié)點(diǎn)的節(jié)點(diǎn)為 n/2 - 1。 n為節(jié)點(diǎn)數(shù)量

利用頂堆的堆積排序：

大/小頂堆的性質(zhì)：

1、頂堆一定是完全二叉樹(shù)，所以可以用數(shù)組直接表示

2、大/小頂堆的每個(gè)子樹(shù)也是大/小頂堆

排序思路：

基本思想：把待排序的元素按照大小在二叉樹(shù)位置上排列，排序好的元素要滿足：父節(jié)點(diǎn)的元素要大于等于其子節(jié)點(diǎn)；這個(gè)過(guò)程叫做堆化過(guò)程，如果根節(jié)點(diǎn)存放的是最大的數(shù)，則叫做大根堆；如果是最小的數(shù)，自然就叫做小根堆了。根據(jù)這個(gè)特性（大根堆根最大，小根堆根最小），就可以把根節(jié)點(diǎn)拿出來(lái)，然后再堆化下，再把根節(jié)點(diǎn)拿出來(lái)，，，，循環(huán)到最后一個(gè)節(jié)點(diǎn)，就排序好了。

參考1：https://blog.csdn.net/YuZhiHui_No1/article/details/44258297

參考2：http://www.seotest.cn/jishu/46956.html

實(shí)現(xiàn)：

1、堆化過(guò)程：從最后一個(gè)分支結(jié)點(diǎn)（n div 2）開(kāi)始，到根（1）為止，依次對(duì)每個(gè)分支結(jié)點(diǎn)進(jìn)行調(diào)整（下沉），以便形成以每個(gè)分支結(jié)點(diǎn)為根的堆，當(dāng)最后對(duì)樹(shù)根結(jié)點(diǎn)進(jìn)行調(diào)整后，整個(gè)樹(shù)就變成了一個(gè)堆。

所謂下沉，即將節(jié)點(diǎn)通過(guò)不斷與自己的子節(jié)點(diǎn)進(jìn)行比較、交換，直到行進(jìn)到某個(gè)位置使得自己是當(dāng)前子樹(shù)中最大或最小的。因?yàn)閱为?dú)的下沉過(guò)程并不能保證子樹(shù)的正確性。所以一定要從最下層有子節(jié)點(diǎn)的節(jié)點(diǎn)開(kāi)始下沉，以保證整體算法的正確性。

2、方法是依次將堆的根節(jié)點(diǎn)數(shù)記下，然后刪除根節(jié)點(diǎn)，如此反復(fù)直到堆為空。上面提到了刪除操作，每次刪除之后都是要調(diào)整堆讓堆的性質(zhì)不變，即根節(jié)點(diǎn)必為最大值或最小值。

具體操作可以使每次都將根節(jié)點(diǎn)與當(dāng)前排序的數(shù)組片段的最后一位互換，然后對(duì)新數(shù)組的第一個(gè)元素進(jìn)行下沉操作（并將進(jìn)行堆化的數(shù)組長(zhǎng)度-1）

由頂堆的性質(zhì)（或根據(jù)堆化的過(guò)程）可知，在排序階段，除每次的頂點(diǎn)外的其他頂點(diǎn)都是已經(jīng)經(jīng)過(guò)下沉操作的，所以直接對(duì)新頂點(diǎn)進(jìn)行下沉即可得到新的頂堆

#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é)點(diǎn) i = size/2 -1 是最后一個(gè)有子節(jié)點(diǎn)的節(jié)點(diǎn)
    // 且i節(jié)點(diǎn)之前的所有節(jié)點(diǎn)都一定有兩個(gè)子樹(shù)
    // 從節(jié)點(diǎn)i開(kāi)始向前，對(duì)所有節(jié)點(diǎn)進(jìn)行下沉操作，保證當(dāng)前節(jié)點(diǎn)下的所有子樹(shù)的正確性
    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ù)組的第一個(gè)值和最后一個(gè)值， mswap僅實(shí)現(xiàn)了數(shù)值交換
        ad_heap(data,0, i);                    // 對(duì)長(zhǎng)度減一的數(shù)組的根節(jié)點(diǎn)進(jìn)行下沉操作
    }
    print_array(data, size);

}


// 該函數(shù)的作用是將節(jié)點(diǎn)i的值下沉到正確位置，并不是將以i為頂點(diǎn)的二叉樹(shù)轉(zhuǎn)為頂堆
// 當(dāng)下沉到某個(gè)節(jié)點(diǎn)，使得i的值比當(dāng)前節(jié)點(diǎn)兩個(gè)子節(jié)點(diǎn)斗大即完成下沉
// 子樹(shù)的正確性由調(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)記左右子樹(shù)中最大的一個(gè)
            if(data[j] < data[j+1]){
                j++;
            }
        }
        if(tmp >= data[j]){                // 如果當(dāng)前節(jié)點(diǎn)比左右子樹(shù)都大則認(rèn)為下沉完成
            post = 1;                      // 不再進(jìn)一步校驗(yàn)下一層的原因是，默認(rèn)子樹(shù)已經(jīng)完成下沉，再進(jìn)行校驗(yàn)就是重復(fù)校驗(yàn)了
        }
        else{
            data[(j-1)/2] = data[j];        // 當(dāng)前節(jié)點(diǎn)小于左節(jié)點(diǎn)或右節(jié)點(diǎn)，需要交換該子節(jié)點(diǎn)的值與當(dāng)前根節(jié)點(diǎn)的值
            j = 2*j + 1;                    // 因?yàn)榘l(fā)生了交換，不能保證交換后的各個(gè)子樹(shù)仍然正確，故需要繼續(xù)對(duì)下一層進(jìn)行檢查
        }
    }
    
    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;
}