理解堆和優(yōu)先隊(duì)列
1 前言
今天一起學(xué)習(xí)一下堆和優(yōu)先隊(duì)列，重點(diǎn)是堆排序的理解和優(yōu)先隊(duì)列的用法。
通過本文你將了解到以下內(nèi)容：
堆的基本原理 堆的調(diào)整函數(shù) 堆排序及其應(yīng)用 優(yōu)先隊(duì)列的概念 優(yōu)先隊(duì)列的原理和應(yīng)用
2 堆
2.1 堆的基本概念
數(shù)據(jù)結(jié)構(gòu)中的堆區(qū)別于內(nèi)存分配的堆，我們說的用于排序的堆是一種表示元素集合的結(jié)構(gòu)，堆是一種二叉樹。
看看維基百科中對于堆的定義和說明：
堆是計(jì)算機(jī)科學(xué)中的一種特別的樹狀數(shù)據(jù)結(jié)構(gòu)。
堆始于J. W. J. Williams在1964年發(fā)表的堆排序，當(dāng)時他提出了二叉堆樹作為此算法的數(shù)據(jù)結(jié)構(gòu)，堆在戴克斯特拉算法和帶優(yōu)先級隊(duì)列中亦為重要的關(guān)鍵。
若是滿足以下特性，即可稱為堆：給定堆中任意節(jié)點(diǎn)P和C，若P是C的母節(jié)點(diǎn)，那么P的值會小于等于C的值。若母節(jié)點(diǎn)的值恒小于等于子節(jié)點(diǎn)的值，此堆稱為最小堆；反之稱為最大堆。
2.2 堆的兩個特性
堆有兩個決定性特性：元素順序和樹的形狀
元素順序
在堆中任何結(jié)點(diǎn)與其子結(jié)點(diǎn)的大小都遵守?cái)?shù)值大小關(guān)系。
A. 如果結(jié)點(diǎn)大于等于其所有子結(jié)點(diǎn)，也就是堆的根是所有元素中最大的，這種堆稱為大根堆(大頂堆、最大堆)；
B. 如果結(jié)點(diǎn)小于等于其所有子結(jié)點(diǎn)，也就是堆的根是所有元素中最小的，這種堆稱為小根堆(小頂堆、最小堆)；
C. 大根堆/小根堆只是約定了父結(jié)點(diǎn)和子結(jié)點(diǎn)的大小關(guān)系，但是并不約束子結(jié)點(diǎn)的相對大小和順序；
如圖為小根堆結(jié)構(gòu)：
樹的形狀
堆這種二叉樹最多在兩層具有葉子結(jié)點(diǎn)，并且最底層的葉子結(jié)點(diǎn)靠左分布，該樹種不存在空閑位置，也就是堆是個完全二叉樹。
上述的兩種性質(zhì)可以保證快捷找到最值，并且在插入和刪除新元素時可以實(shí)現(xiàn)重新組織再次滿足堆的性質(zhì)。
2.3 堆的數(shù)組表示
堆中沒有空閑位置并且數(shù)組是連續(xù)的，但是數(shù)組的下標(biāo)是從0開始，為了統(tǒng)一，我們統(tǒng)一從1開始，也就是root結(jié)點(diǎn)的數(shù)組index=1，那么可以通過數(shù)組的index可以通過父結(jié)點(diǎn)找到左右子結(jié)點(diǎn)，也可以通過子結(jié)點(diǎn)找到父結(jié)點(diǎn)。
數(shù)組的元素遍歷就是堆的層次遍歷的結(jié)果，因此數(shù)組存儲的堆具備以下性質(zhì)：
//數(shù)組下標(biāo)范圍
i<=n?&&?i>=1
//根結(jié)點(diǎn)下標(biāo)為1
root_index?=?1
//層次遍歷第i個結(jié)點(diǎn)的值等于數(shù)組第i個元素
value(i)?=?array[i]
//堆中第i個元素的左孩子下標(biāo)i*2
left_child_index(i)?=?i*2
//堆中第i個元素的右孩子下標(biāo)i*2+1
right_child_index(i)?=?i*2+1
//堆中第i個元素的父結(jié)點(diǎn)下標(biāo)i/2
parent(i)?=?i/2
2.4 堆的調(diào)整函數(shù)
堆調(diào)整的過程非常像數(shù)學(xué)歸納法的遞推過程，看一下就知道，敲黑板！以下兩個函數(shù)對于掌握堆非常重要。
2.4.1 siftup函數(shù)的原理
以小根堆為例，之前a[1...n-1]滿足堆的特性，在數(shù)組a[n]插入新元素之后，就產(chǎn)生了兩種情況：
A. 如果a[n]大于父結(jié)點(diǎn)那么a[1...n]仍然滿足堆的特性，不需要調(diào)整；
B. 如果a[n]比它的父結(jié)點(diǎn)要小無法保證堆的特性，就需要進(jìn)行調(diào)整；
循環(huán)過程：自底向上的調(diào)整過程就是新加入元素不斷向上比較置換的過程，直到新結(jié)點(diǎn)的值大于其父結(jié)點(diǎn)，或者新結(jié)點(diǎn)成為根結(jié)點(diǎn)為止。
停止條件：siftup是一個不斷向上循環(huán)比較置換的過程，理解循環(huán)的關(guān)鍵是循環(huán)停止的條件，從偽碼中可以清晰地看到，siftup的偽碼：
//siftup運(yùn)行的前置條件
heap(1,n-1)?==?True
void?siftup(n)
?????i?=?n
?????loop:
?????????//?循環(huán)停止條件一
?????????//?已經(jīng)是根結(jié)點(diǎn)
?????????if?i?==?1:
?????????????break;
?????????p?=?i/2
?????????//?循環(huán)停止條件二
?????????//?調(diào)整結(jié)點(diǎn)大于等于在此位置的父結(jié)點(diǎn)
?????????if?a[p]?<=?a[i]
??????????????break;
?????????swap(a[p],a[i])
?????????//?繼續(xù)向上循環(huán)
?????????i?=?psiftup調(diào)整過程演示
2.4.2 siftdn函數(shù)的原理
以小根堆為例，之前a[1...n]滿足堆的特性，在數(shù)組a[1]更新元素之后，就產(chǎn)生了兩種情況：
A. 如果a[1]小于等于子結(jié)點(diǎn)仍然滿足堆的特性，不需要調(diào)整；
B. 如果a[1]大于子結(jié)點(diǎn)無法保證堆的特性，就需要進(jìn)行調(diào)整；
循環(huán)過程：自頂向下的調(diào)整過程就是新加入元素不斷向下比較置換的過程，直到新結(jié)點(diǎn)的值小于等于其子結(jié)點(diǎn)，或者新結(jié)點(diǎn)成為葉結(jié)點(diǎn)為止。
停止條件：siftdn是一個不斷向下循環(huán)比較置換的過程，理解循環(huán)的關(guān)鍵是循環(huán)停止的條件，從偽碼中可以清晰地看到siftdn的偽碼:
heap(2,n)?==?True
void?siftdn(n)
?????i?=?1
?????loop:
?????????//?獲取理論上的左孩子下標(biāo)
?????????c?=?2*i
?????????//?如果左孩子下標(biāo)已經(jīng)越界?
?????????//?說明當(dāng)前已經(jīng)是葉子結(jié)點(diǎn)
?????????if?c?>?n:
?????????????break;
?????????//如果存在右孩子?
?????????//?則獲取左右孩子中更小的一個
?????????//?和父結(jié)點(diǎn)比較
?????????if?c+1?<=?n:
?????????????if?a[c]?>?a[c+1]
?????????????????c++
?????????//?父結(jié)點(diǎn)小于等于左右孩子結(jié)點(diǎn)則停止
?????????if?a[i]?<=?a[c]
?????????????break;
?????????//?父結(jié)點(diǎn)比左右孩子結(jié)點(diǎn)大?
?????????//?則與其中較小的孩子結(jié)點(diǎn)交換
?????????//?也就是讓原來的孩子結(jié)點(diǎn)成為父結(jié)點(diǎn)
?????????swap(a[i],a[c])
?????????//?繼續(xù)向下循環(huán)
?????????i?=?c?????siftdn調(diào)整過程演示
在頭部元素更新為21的調(diào)整過程如圖：
2.5 堆排序
場景：假如有200w數(shù)據(jù)，要找最大的前10個數(shù)。
分析：那么就需要先建立大小為10個元素的小頂堆，然后再逐漸把其他所有元素依次滲透進(jìn)來比較或入堆淘汰老數(shù)據(jù)或跳過，直至所有數(shù)據(jù)滲透完成，最后小根堆的10個元素就是最大的10個數(shù)了。
小根堆：選擇最大的TopN個數(shù)據(jù)使用小根堆，因?yàn)槎秧斁褪亲钚〉臄?shù)據(jù)，每次進(jìn)來的新數(shù)據(jù)只需要和堆頂比較即可，如果小于堆頂則跳過，如果大于堆頂則替換掉堆頂進(jìn)行siftdn調(diào)整，來找到新進(jìn)元素的正確位置，以及產(chǎn)生新的堆頂。
建堆過程：可以自頂向下自底向上均可，以下采用自底向上思路分析。可以將數(shù)組的葉子節(jié)點(diǎn)，是單個結(jié)點(diǎn)滿足二叉堆的定義，于是從底層葉子結(jié)點(diǎn)的父結(jié)點(diǎn)從左到右，逐個向上構(gòu)建二叉堆，直到第一個節(jié)點(diǎn)時整個數(shù)組就是一個二叉堆，這個過程是siftup和siftdn的混合，宏觀上來看是自底向上，微觀上每個父結(jié)點(diǎn)是自頂向下。
滲透排序過程：完成堆化之后，開處理N之后的元素，從N+1~200w，遇到比當(dāng)前堆頂大的則與堆頂元素交換，進(jìn)入堆觸發(fā)siftdn調(diào)整，直至生產(chǎn)新的小根堆。
代碼實(shí)戰(zhàn)：leetCode 第215題 數(shù)組中的第K個最大元素。
這道題可以用堆排序來完成，建立小根堆取堆頂元素即可，驗(yàn)證通過的代碼舉例：
//leetcode?215th?the?Kth?Num
//Source?Code:C++
class?Solution?{
public:
????//調(diào)整以當(dāng)前節(jié)點(diǎn)為根的子樹為小頂堆
????int?heapadjust(vector<int>?&nums,int?curindex,int?len){
????????int?curvalue?=?nums[curindex];
????????int?child?=?curindex*2+1;
????????while(child????????????//左右孩子中較小的那個
????????????if(child+1?nums[child+1]){
????????????????child++;
????????????}
????????????//當(dāng)前父節(jié)點(diǎn)比左右孩子其中一個大
????????????if(curvalue?>?nums[child]){
????????????????nums[curindex]=nums[child];
????????????????curindex?=?child;
????????????????child?=?curindex*2+1;?
????????????}else{
????????????????break;
????????????}
????????}
????????nums[curindex]=curvalue;
????????return?0;
????}
????int?findKthLargest(vector<int>&?nums,?int?k)?{
????????//邊界條件
????????if(nums.size()????????????return?-1;
????????//建立元素只有K個的小頂堆
????????//截取數(shù)組的前k個元素
????????vector<int>?subnums(nums.begin(),nums.begin()+k);
????????int?len?=?nums.size();
????????int?sublen?=?subnums.size();
????????//將數(shù)組的前k個元素建立小頂堆
????????for(int?i=sublen/2-1;i>=0;i--){
????????????heapadjust(subnums,i,sublen);
????????}
????????//建立好小頂堆之后?開始逐漸吸收剩余的數(shù)組元素
????????//動態(tài)與堆頂元素比較?替換
????????for(int?j=k;j????????????if(nums[j]<=subnums[0])
????????????????continue;
????????????subnums[0]?=?nums[j];
????????????heapadjust(subnums,0,sublen);
????????}
????????return?subnums[0];??
????}
}; 2.6 堆小結(jié)
從實(shí)踐來看，堆的重要用途是堆排序，堆排序重點(diǎn)是初始化堆和調(diào)整堆兩個過程，然而這兩個過程都離不開siftup和siftdn兩個函數(shù)，因此掌握這兩個函數(shù)，基本上就掌握了堆。
由于堆是二叉樹，因此在實(shí)際使用中需要結(jié)合樹的遍歷和循環(huán)來實(shí)現(xiàn)堆調(diào)整，掌握堆調(diào)整過程和二叉樹遍歷過程，拿下堆，指日可待。
3 優(yōu)先隊(duì)列
先來看看維基百科對優(yōu)先隊(duì)列的定義：
優(yōu)先隊(duì)列是計(jì)算機(jī)科學(xué)中的一類抽象數(shù)據(jù)類型。?
優(yōu)先隊(duì)列中的每個元素都有各自的優(yōu)先級，優(yōu)先級最高的元素最先得到服務(wù)；優(yōu)先級相同的元素按照其在優(yōu)先隊(duì)列中的順序得到服務(wù)。
優(yōu)先隊(duì)列至少需要支持下述操作：
a.插入帶優(yōu)先級的元素?
b.取出具有最高優(yōu)先級的元素
c.查看最高優(yōu)先級的元素。
綜合考慮插入和刪除的性能 優(yōu)先隊(duì)列一般采用堆來實(shí)現(xiàn)。
由于優(yōu)先隊(duì)列的元素既可以是基礎(chǔ)類型，也可以是復(fù)合類型，因此在C++中一般使用模板來定義優(yōu)先隊(duì)列，從而提高其可擴(kuò)展性，簡單定義：
template<class?T>
class?priqueue?{
public:
???????//構(gòu)造函數(shù)?初始化
???????priqueue(int?maxsize);
???????//將T類型新元素添加到隊(duì)列中
???????void?insert(T?t);
???????//獲取隊(duì)列中最小的元素
???????T?extractmin();
};3.1 優(yōu)先隊(duì)列的理論實(shí)現(xiàn)
實(shí)現(xiàn)優(yōu)先隊(duì)列的候選數(shù)據(jù)結(jié)構(gòu)包括：有序序列、無序序列、堆。
有序序列
有序序列中存儲的數(shù)據(jù)都是有序的，在執(zhí)行extractmin獲取最小值時復(fù)雜度O(1)，但是在添加新元素時就存在大量的移動和查找正確的位置最大復(fù)雜度O(N)，因此在insert和extactmin同時執(zhí)行N次時，最大復(fù)雜度為O(N^2)。無序序列
無序序列中存儲的元素是無序的，在執(zhí)行insert操作復(fù)雜度為O(1)，但是在extractmin時每次都要進(jìn)行一次遍歷復(fù)雜度為O(N)，因此在insert和extractmin同時執(zhí)行N次時，最大復(fù)雜度為O(N^2)。堆結(jié)構(gòu)
從上一節(jié)我們知道堆的insert不如無序序列那么隨意，extractmin也沒有有序序列那么容易，每次都需要進(jìn)行siftup和siftdn操作進(jìn)行調(diào)整，但是同時執(zhí)行insert和extractmin時，復(fù)雜度是O(nlogn)，優(yōu)于O(N^2)。
綜上可知，堆結(jié)構(gòu)在實(shí)現(xiàn)優(yōu)先隊(duì)列的插入和刪除操作時復(fù)雜性都很穩(wěn)定，在大量數(shù)據(jù)的場景下優(yōu)于有序序列和無序序列，因此權(quán)衡之下選擇堆作為優(yōu)先隊(duì)列的底層數(shù)據(jù)結(jié)構(gòu)。
3.2?優(yōu)先隊(duì)列的工程實(shí)現(xiàn)
考慮優(yōu)先隊(duì)列的靈活性和效率，可以基于模板化和堆來實(shí)現(xiàn)優(yōu)先隊(duì)列：
template<class?T>
class?priqueue?{
????private:
????????int?n,maxsize;
????????T?*x;
????????void?swap(int?i,int?j)
????????{?T?t?=?x[i];?x[i]?=?x[j];?x[j]?=?t;?}
????public:
????????//初始化
????????priqueue(int?m)
????????{?
????????????maxsize?=?m;
????????????x?=?new?T[maxsize+1];
????????????n?=?0;
????????}
????????//插入新數(shù)據(jù)
????????void?insert(T?t)
????????{?
????????????int?i,p;
????????????x[++n]?=?t;
????????????//末尾添加新數(shù)據(jù)?執(zhí)行siftup操作
????????????for?(i?=?n;?i?>?1?&&?x[p=i/2]?>?x[i];?i?=?p)
????????????????swap(p,i);
????????}
????????//提取操作
????????T?extractmin()
???????{
??????????int?i,c;
??????????//提取堆頂元素
??????????T?t?=?x[1];
??????????//將尾部元素放到堆頂
??????????x[1]?=?x[n--];
??????????//針對新堆頂進(jìn)行siftdn操作
??????????for?(i?=?1;?(c?=?2*i)?<=?n;?i?=?c)?{
??????????????if?(c+1?<=?n?&&?x[c+1]????????????????????c++;
??????????????if?(x[i]?<=?x[c])
???????????????????break;
???????????????swap(c,i);
??????????}
?????????return?t;
??????}
};上述代碼摘自編程珠璣并不是STL關(guān)于優(yōu)先隊(duì)列的實(shí)現(xiàn)，只是一部分簡潔的代碼，旨在表現(xiàn)insert和extract操作時如何運(yùn)用堆的siftup和siftdn操作來封裝成優(yōu)先隊(duì)列類的基礎(chǔ)成員函數(shù)。?
3.3 優(yōu)先隊(duì)列的自定義優(yōu)先級
模板化的優(yōu)先隊(duì)列擴(kuò)展了使用場景，但是也產(chǎn)生了新的問題，就是默認(rèn)的優(yōu)先級比較函數(shù)不一定滿足所有要求，因此很多時候都需要自己來定義優(yōu)先級判定函數(shù)。
實(shí)現(xiàn)了一個模板優(yōu)先隊(duì)列需要三個參數(shù)：?
容器元素的類型
存儲數(shù)據(jù)所用的容器
比較函數(shù) 缺省情況是less
#include
//?隊(duì)列和優(yōu)先隊(duì)列的聲明
std::queue?pq;
std::priority_queuestd::vector,?cmp>?pq;
//模板化優(yōu)先隊(duì)列的主要參數(shù)
priority_queue
//舉例
priority_queuechar,int>,vectorchar,int>>,compare>?pq;
//自定義比較函數(shù)
struct?compare
{
????bool?operator()(const?pair<char,int>?a,const?pair<char,int>?b){
????????return?b.second?>?a.second;
????}??
}; 3.4?優(yōu)先隊(duì)列的應(yīng)用
可以認(rèn)為優(yōu)先隊(duì)列是對堆的工具化封裝，加上模板和自定義比較函數(shù)兩個利器加持，優(yōu)先隊(duì)列讓使用者不再苦于堆排序的原始造輪子。
TopN問題和優(yōu)先隊(duì)列
仍以LeetCode 215題為例，獲取數(shù)組第K大元素。
上一節(jié)中我們直接使用堆，但是構(gòu)建的是小頂堆，并且大小是K個元素，遍歷完成之后直接取堆頂即可，但是在數(shù)據(jù)量不大或者內(nèi)存足夠的情況下，可以直接建立優(yōu)先隊(duì)列。?
默認(rèn)的優(yōu)先隊(duì)列本質(zhì)上是大頂堆，那么堆頂就不是第K大元素了，但是從堆頂開始依次pop出K-1個元素，堆頂也就是第K大元素了。?
當(dāng)然也可以修改比較函數(shù)實(shí)現(xiàn)小頂堆，取堆頂元素也是可以的，要靈活運(yùn)用。使用優(yōu)先隊(duì)列實(shí)現(xiàn)LeetCode 第215題，代碼如下：
//默認(rèn)的比較函數(shù)是less?也就是優(yōu)先隊(duì)列相當(dāng)于最大堆
//堆頂元素為最大值
priority_queue<int,vector<int>,less<int>>?q;
int?findKthLargest(vector<int>&?nums,?int?k)?
{
??priority_queue<int>?q(nums.begin(),nums.end());
??for(int?i=0;i-1;i++)?
??????q.pop();
??return?q.top();
} 優(yōu)先隊(duì)列是貪心算法的重要組成部分，借助于優(yōu)先隊(duì)列貪心算法可以解決非常多的實(shí)際問題包括：
旅行商TSP問題 01背包問題 霍夫曼編碼問題 最短路徑Dijkstra算法 最小生成樹Prim算法
巨人的肩膀
《編程珠璣》 http://www.laicar.com/book/echapter/5cb0a77e739207662ac8710c/links/item10/OEBPS/Text/part0009.xhtml https://my.oschina.net/u/1246663/blog/227115