前言

堆（二叉堆），一種動(dòng)態(tài)的樹(shù)型結(jié)構(gòu)，一種除了底層外，完全被填滿(mǎn)的二叉樹(shù)結(jié)構(gòu)。因此，堆一般是基于數(shù)組去實(shí)現(xiàn)的，它不會(huì)出現(xiàn)數(shù)組中很多空缺的現(xiàn)象，而造成空間浪費(fèi)。如下是一個(gè)完全二叉樹(shù)：

完全二叉樹(shù)

它可以用數(shù)組表示為[10,7,2,5,1]，若以k表示當(dāng)前數(shù)組的索引，那么：

• 其父節(jié)點(diǎn)：floor((k-1)/2)
• 其左孩子：2k+1
• 其又孩子：2k+2

結(jié)合上圖，堆的性質(zhì)如下：

• 堆必須是完全二叉樹(shù)；
• 任一節(jié)點(diǎn)要么比其子樹(shù)節(jié)點(diǎn)大，要么??；
• 根據(jù)上面性質(zhì)，堆被分為最大堆（大頂堆）和最小堆（小頂堆）。

堆的主要用途:

• 構(gòu)建優(yōu)先隊(duì)列；
• 支持堆排序；
• 快速找出集合中的最大值或最小值。

堆結(jié)構(gòu)的基本操作(以最大堆為例，本文均使用vector容器存儲(chǔ)數(shù)組，假設(shè)vector容器的基本操作時(shí)間復(fù)雜度為Θ(1))：

• MaxHeap：維護(hù)最大堆的性質(zhì)，時(shí)間復(fù)雜度O(nlgn)；
• BuildHeap：從無(wú)序的輸入數(shù)據(jù)構(gòu)造一個(gè)最大堆，時(shí)間復(fù)雜度為O(n)；

堆結(jié)構(gòu)的基本操作

1.MaxHeap：
輸入一個(gè)數(shù)組A和一個(gè)下標(biāo)i，使不滿(mǎn)足最大堆性質(zhì)的A[i]逐級(jí)下降，直到滿(mǎn)足。

void MaxHeap(vector<int> &A, int i){
    int max; //存儲(chǔ)父節(jié)點(diǎn)和其子樹(shù)節(jié)點(diǎn)中的最大值下標(biāo)
    int lef_child = 2i;      //左孩子
    int rig_child = 2i + 1;  //右孩子
    //左孩子大于父節(jié)點(diǎn)
    if(lef_child <= A.size() && A[lef_child] > A[i])
        max = lef_child;   
    else max = i;
    //右孩子更大
    if(rig_child <= A.size() && A[rig_child] > A[max])
        max = rig_child;  
    
    //將最大值上移至父節(jié)點(diǎn)
    if(max != i){
        //交換
        int temp = A[i]; A[i] = A[max]; A[max] = temp;
        //更新了數(shù)組，需繼續(xù)查看當(dāng)前元素是否滿(mǎn)足最大堆性質(zhì)
        MaxHeap(A, max);  
    }
}

因?yàn)槊恳粋€(gè)節(jié)點(diǎn)的子樹(shù)節(jié)點(diǎn)數(shù)(包括孩子的孩子)至多為2n/3(n是整個(gè)樹(shù)的節(jié)點(diǎn)數(shù)，最壞情況即節(jié)點(diǎn)為根節(jié)點(diǎn)，且底層大于等于半滿(mǎn))，所以該算法的時(shí)間復(fù)雜度為T(n) <= T(2n/3) + Θ(1)通過(guò)主方法求解得T(n)=O(lgn)，最后因?yàn)楹琻個(gè)元素的堆高為O(lgn)，所以其時(shí)間復(fù)雜度又可以表示為O(h)。

2.BuildHeap：
可以通過(guò)自底向上的方法，從最后一個(gè)葉節(jié)點(diǎn)開(kāi)始倒序遍歷，并調(diào)用MaxHeap判斷當(dāng)前節(jié)點(diǎn)子樹(shù)是否滿(mǎn)足最大堆性質(zhì)。

void BuildHeap(vector<int> &A){
    int i = A.size()/2; //最后一個(gè)非葉節(jié)點(diǎn)的位置
    for(i; i >= 0; i--)  //自底向上維護(hù)
        MaxHeap(A, i);
}

該算法的時(shí)間復(fù)雜度很容易通過(guò)，循環(huán)n次，每次調(diào)用MaxHeap耗費(fèi)O(lgn)，從而得出T(n)=O(nlgn)，雖然正確，但是該算法上界還可以繼續(xù)緊確。

一個(gè)含n個(gè)元素的堆高(最底層高為0)為floor(lgn)，而該堆最多包含ceil(n/2^(h+1))個(gè)高度為h的節(jié)點(diǎn)。而一個(gè)高度為h的節(jié)點(diǎn)運(yùn)行MaxHeap的時(shí)間復(fù)雜度為O(h)，所以可以將BuildHeap的總代價(jià)表示為：

BuildHeap的總代價(jià)

構(gòu)建一個(gè)優(yōu)先隊(duì)列

1.什么是優(yōu)先隊(duì)列
優(yōu)先隊(duì)列是一種特殊的隊(duì)列，它不按先進(jìn)先出的原則，而是以優(yōu)先度來(lái)彈出元素。它本質(zhì)是一種用來(lái)維護(hù)由一組元素構(gòu)成的集合S的數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)元素都有一個(gè)相關(guān)的值，稱(chēng)為關(guān)鍵字。和堆一樣，優(yōu)先隊(duì)列也分為最大優(yōu)先隊(duì)列和最小優(yōu)先隊(duì)列。

2.優(yōu)先隊(duì)列的相關(guān)操作
HeapTop: 返回并刪除掉當(dāng)前堆頂，時(shí)間復(fù)雜度為O(lgn)。

int HeapTop(vector<int> &A){
    if(A.size() < 1) exit(0); //沒(méi)有元素    
    int max = A[0];
    //堆頂?shù)扔谧詈笠粋€(gè)值，并將最后一個(gè)值彈出
    A[0] = A[A.size()-1];
    A.push_pop();
    //維護(hù)最大堆性質(zhì)
    MaxHeap(A, 0);
    return max;
}

HeapInsert：插入一個(gè)元素到當(dāng)前堆中，時(shí)間復(fù)雜度為O(lgn)。

void HeapInsert(vector<int> &A, k){
    A.push_back(A[0]);
    A[0] = k;
    //維護(hù)最大堆性質(zhì)
    MaxHeap(A, 0);
}

STL中堆與優(yōu)先隊(duì)列的實(shí)現(xiàn)

1.堆
heap不屬于STL中的容器組件，它是以算法的形式呈現(xiàn)，“默默扮演著幕后英雄”。heap默認(rèn)是最大堆排序。使用方法如下：

vector<int> ivec{0, 1, 2};
//最大堆[2, 1, 0]
make_heap(ivec.begin(), ivec.end()); 
ivec.push_back(5);
//在堆的基礎(chǔ)上進(jìn)行數(shù)據(jù)插入[5, 2, 0, 1]
push_heap(ivec.begin(), ivec.end());
//pop_heap并沒(méi)有刪除元素，而是將堆頂元素與最后一個(gè)元素進(jìn)行了替換
//[2, 1, 0, 5]
pop_heap(ivec.begin(), ivec.end());
//刪除堆頂?shù)脑豙2, 1, 0]
ivec.pop_back();
//默認(rèn)小堆排序[0, 1, 2]
sort_heap(ivec.begin(), ivec.end());

2.優(yōu)先隊(duì)列
priority_queue是STL中優(yōu)先隊(duì)列的名稱(chēng)，默認(rèn)也是最大堆排序。使用方法如下：

priority_queue<int> que;
que.push(x); //每次push之后會(huì)自動(dòng)維護(hù)，保證堆頂是優(yōu)先級(jí)別最高的
que.pop();
que.top();

priority_queue還可以自定義存儲(chǔ)的數(shù)據(jù)類(lèi)型以及排序方式，具體應(yīng)用可以【關(guān)注公眾號(hào)DoCode，每日一道LeetCode，將零碎時(shí)間利用起來(lái)】回復(fù)關(guān)鍵字“堆”查看。