今天，我們來(lái)談一談一個(gè)很常用的數(shù)據(jù)結(jié)構(gòu)---堆匕争。
堆（Heap）避乏，也叫優(yōu)先隊(duì)列（Priority Queue）。
是一種完全二叉樹(shù)甘桑，樹(shù)根是整個(gè)樹(shù)最大或最小的元素拍皮。（對(duì)應(yīng)的就是最大堆和最小堆，后文討論最大堆）
先來(lái)看一個(gè)最大堆的例子吧

1.JPG

可以看到56是整個(gè)堆最大的元素跑杭，接著對(duì)于19來(lái)說(shuō)铆帽，19又是以它為根的堆的最大的元素，40也是德谅。

由于是完全二叉樹(shù)爹橱，所以用數(shù)組來(lái)存儲(chǔ)堆，比用鏈表來(lái)存儲(chǔ)堆要方便許多窄做。
哦愧驱，對(duì)了，好像還沒(méi)說(shuō)什么是完全二叉樹(shù)吧椭盏，完全二叉樹(shù)就是二叉樹(shù)是滿的冯键，如果不是完全二叉樹(shù)，這棵樹(shù)可能長(zhǎng)成這個(gè)樣子庸汗。。

2.JPG

class Heap{
protected:
    int *data;
    int size;
    int Capcity;
    Heap(int size):size(0),Capcity(size) {
        data = new int[size + 1];
        data[0]=MaxData;
    }
}

Heap（n）的構(gòu)造函數(shù)蛆楞，給我一個(gè)n溯乒，我就創(chuàng)造一個(gè)容量為n的堆，動(dòng)態(tài)分配n+1個(gè)空間給數(shù)組豹爹，同時(shí)數(shù)組的下標(biāo)0設(shè)置成哨兵裆悄。（后文會(huì)講什么是哨兵）

對(duì)于堆來(lái)說(shuō)，我們主要的操作是插入和刪除臂聋，真正的難點(diǎn)在于光稼，我們要保證我們插入和刪除了之后，仍是一個(gè)最大堆或最小堆逻住。
以最大堆為例钟哥，如果我們?cè)诙阎胁迦肓艘粋€(gè)新元素（如圖3），

圖3

那么實(shí)質(zhì)是我們?cè)诙阎袛?shù)組的7號(hào)位置存放我們的新元素瞎访，如果插入的元素比44小腻贰，那還是堆，但一旦插入的元素大于44扒秸，甚至大于58播演，那就不是堆了，我們的解決辦法是什么伴奥？

交換元素的位置写烤。

怎么個(gè)交換法？我們插入的元素要跟父節(jié)點(diǎn)的元素比拾徙，大的話就交換洲炊，交換好了就繼續(xù)再跟父節(jié)點(diǎn)的父節(jié)點(diǎn)比，如果還大就接著交換尼啡。
所以暂衡，如果我們插入了60，那么60的下標(biāo)是7崖瞭，父節(jié)點(diǎn)是7/2=3狂巢，60和44比，發(fā)現(xiàn)大书聚，就交換唧领，44換到下標(biāo)為7的位置，而3的位置放著60雌续，接著3/2=1斩个，60去和58比，比58大西雀，接著交換萨驶，就這樣一直循環(huán)下去。
最后如果換到了下標(biāo)為1（也就是我們現(xiàn)在的情況）艇肴，下標(biāo)為1的父節(jié)點(diǎn)就會(huì)是哨兵了腔呜，所以叁温，只要我們?cè)O(shè)置哨兵的值比任何值都大，我們的循環(huán)就一定會(huì)停止核畴。

所以插入的代碼如下膝但。

    void push(int x){
        if(full()){//判斷堆是否還沒(méi)滿
            cout<<"full push"<<endl;
            return;
        }
        int i=++size;
        for(;x>data[i/2];i/=2)
            data[i]=data[i/2];
        data[i]=x;
    }

現(xiàn)在，讓我們看一看刪除是怎么回事谤草。
刪除其實(shí)就是彈出根節(jié)點(diǎn)（最大的元素）跟束。

圖3

還是圖3，首先我們彈出了58丑孩，然而解決方法還是交換~
首先我們把最后一個(gè)元素冀宴，下標(biāo)為6的31提拔到根節(jié)點(diǎn)處，

圖4

然后去跟兩個(gè)兒子比温学，如果比較大的那個(gè)兒子（也就是44）的元素值大于父節(jié)點(diǎn)（也就是現(xiàn)在的31）略贮，就 交換 ！仗岖！
然后就循環(huán)直到?jīng)]有兒子為止逃延，或者不用交換為止！

所以轧拄，
刪除的代碼如下：

    int pop(){
        if(empty()){//判斷是否空
            cout<<"empty pop"<<endl;
            return MaxData;
        }
        int x=data[1];
        int temp=data[size--];
        if(size==0)return x;
        int Parent=1;
        int child;
        while(2*Parent<=size){//Parent有兒子
            child=Parent*2;
            if(child+1<=size&&data[child]<data[child+1]){//指向child中較大的一個(gè)
                child++;
            };
            if(temp>=data[child])break;
            data[Parent]=data[child];
            Parent=child;
        }
        data[Parent]=temp;
        return x;
    }

最后揽祥，讓我們來(lái)談一談堆排序，什么是堆排序呢檩电？
堆排序就是比如說(shuō)我告訴你我要你插入n個(gè)數(shù)拄丰，然后你就先把n個(gè)數(shù)一一填到堆的數(shù)組中，注意俐末，不是插入愈案，填完以后并不是堆，而是就像普通的數(shù)組一樣鹅搪，都填完了，再進(jìn)行整體的排序遭铺，排成堆丽柿。

我們的做法是這樣的，對(duì)于數(shù)組魂挂，從第一個(gè)有兒子的下標(biāo)開(kāi)始甫题，進(jìn)行排堆操作，一直排到下標(biāo)為1為止涂召，什么是排堆操作呢坠非？
就是把以該節(jié)點(diǎn)為根節(jié)點(diǎn)，建成一個(gè)堆果正，代碼和刪除的代碼很像Ｑ茁搿盟迟！
（把該節(jié)點(diǎn)與兩兒子中的大的比較，然后如果兒子大就交換潦闲，否則就停止Ｔ懿ぁ）幾乎可以把刪除的后半部分代碼復(fù)制成排堆操作的代碼。

下面給出代碼：

protected:
    void Sorted(int i){//所謂的堆排序
        int temp=data[i];
        int child;
        while(2*i<=size){
            child=2*i;
            if(child+1<=size&&data[child]<data[child+1])
                child++;
            if(temp>=data[child])break;
            data[i]=data[child];
            i=child;
        }
        data[i]=temp;
    }

public:
    void build(int n){
        if(n>Capcity){
            cout<<"n is greater than Capcity"<<endl;
            return;
        }
        int x;
        for(int i=1;i<=n;i++){
            cin>>x;
            data[i]=x;
        }
        int i=size=n;
        i/=2;//第一個(gè)有兒子的結(jié)點(diǎn)
        for(;i>=1;i--){
            Sorted(i);
        }
    }

值得注意的是：堆排序的時(shí)間復(fù)雜度居然是o（n）Ｇ溉颉辖众！

參考視頻鏈接：https://www.icourse163.org/learn/ZJU-93001?tid=1003013004#/learn/content?type=detail&id=1004242210&cid=1005239493