理解堆和優(yōu)先隊列

1 前言

今天一起學習一下堆和優(yōu)先隊列，重點是堆排序的理解和優(yōu)先隊列的用法。

通過本文你將了解到以下內容：

• 堆的基本原理
• 堆的調整函數(shù)
• 堆排序及其應用
• 優(yōu)先隊列的概念
• 優(yōu)先隊列的原理和應用

2 堆

2.1 堆的基本概念

數(shù)據結構中的堆區(qū)別于內存分配的堆，我們說的用于排序的堆是一種表示元素集合的結構，堆是一種二叉樹。

看看維基百科中對于堆的定義和說明：

堆是計算機科學中的一種特別的樹狀數(shù)據結構。

堆始于J. W. J. Williams在1964年發(fā)表的堆排序，當時他提出了二叉堆樹作為此算法的數(shù)據結構，堆在戴克斯特拉算法和帶優(yōu)先級隊列中亦為重要的關鍵。

若是滿足以下特性，即可稱為堆：給定堆中任意節(jié)點P和C，若P是C的母節(jié)點，那么P的值會小于等于C的值。若母節(jié)點的值恒小于等于子節(jié)點的值，此堆稱為最小堆；反之稱為最大堆。

2.2 堆的兩個特性

堆有兩個決定性特性：元素順序和樹的形狀

• 元素順序

在堆中任何結點與其子結點的大小都遵守數(shù)值大小關系。

A. 如果結點大于等于其所有子結點，也就是堆的根是所有元素中最大的，這種堆稱為大根堆(大頂堆、最大堆)；

B. 如果結點小于等于其所有子結點，也就是堆的根是所有元素中最小的，這種堆稱為小根堆(小頂堆、最小堆)；

C. 大根堆/小根堆只是約定了父結點和子結點的大小關系，但是并不約束子結點的相對大小和順序；

如圖為小根堆結構：

• 樹的形狀

堆這種二叉樹最多在兩層具有葉子結點，并且最底層的葉子結點靠左分布，該樹種不存在空閑位置，也就是堆是個完全二叉樹。

上述的兩種性質可以保證快捷找到最值，并且在插入和刪除新元素時可以實現(xiàn)重新組織再次滿足堆的性質。

2.3 堆的數(shù)組表示

堆中沒有空閑位置并且數(shù)組是連續(xù)的，但是數(shù)組的下標是從0開始，為了統(tǒng)一，我們統(tǒng)一從1開始，也就是root結點的數(shù)組index=1，那么可以通過數(shù)組的index可以通過父結點找到左右子結點，也可以通過子結點找到父結點。

數(shù)組的元素遍歷就是堆的層次遍歷的結果，因此數(shù)組存儲的堆具備以下性質：

//數(shù)組下標范圍
i<=n?&&?i>=1
//根結點下標為1
root_index?=?1
//層次遍歷第i個結點的值等于數(shù)組第i個元素
value(i)?=?array[i]
//堆中第i個元素的左孩子下標i*2
left_child_index(i)?=?i*2
//堆中第i個元素的右孩子下標i*2+1
right_child_index(i)?=?i*2+1
//堆中第i個元素的父結點下標i/2
parent(i)?=?i/2

堆和數(shù)組的對應關系如圖：

2.4 堆的調整函數(shù)

堆調整的過程非常像數(shù)學歸納法的遞推過程，看一下就知道，敲黑板！以下兩個函數(shù)對于掌握堆非常重要。

2.4.1 siftup函數(shù)的原理

以小根堆為例，之前a[1...n-1]滿足堆的特性，在數(shù)組a[n]插入新元素之后，就產生了兩種情況：
A. 如果a[n]大于父結點那么a[1...n]仍然滿足堆的特性，不需要調整；
B. 如果a[n]比它的父結點要小無法保證堆的特性，就需要進行調整；

循環(huán)過程：自底向上的調整過程就是新加入元素不斷向上比較置換的過程，直到新結點的值大于其父結點，或者新結點成為根結點為止。
停止條件：siftup是一個不斷向上循環(huán)比較置換的過程，理解循環(huán)的關鍵是循環(huán)停止的條件，從偽碼中可以清晰地看到，siftup的偽碼：

//siftup運行的前置條件
heap(1,n-1)?==?True
void?siftup(n)
?????i?=?n
?????loop:
?????????//?循環(huán)停止條件一
?????????//?已經是根結點
?????????if?i?==?1:
?????????????break;
?????????p?=?i/2
?????????//?循環(huán)停止條件二
?????????//?調整結點大于等于在此位置的父結點
?????????if?a[p]?<=?a[i]
??????????????break;
?????????swap(a[p],a[i])
?????????//?繼續(xù)向上循環(huán)
?????????i?=?p

siftup調整過程演示

在尾部插入元素16的調整過程如圖：

2.4.2 siftdn函數(shù)的原理

以小根堆為例，之前a[1...n]滿足堆的特性，在數(shù)組a[1]更新元素之后，就產生了兩種情況：
A. 如果a[1]小于等于子結點仍然滿足堆的特性，不需要調整；
B. 如果a[1]大于子結點無法保證堆的特性，就需要進行調整；

循環(huán)過程：自頂向下的調整過程就是新加入元素不斷向下比較置換的過程，直到新結點的值小于等于其子結點，或者新結點成為葉結點為止。
停止條件：siftdn是一個不斷向下循環(huán)比較置換的過程，理解循環(huán)的關鍵是循環(huán)停止的條件，從偽碼中可以清晰地看到siftdn的偽碼:

heap(2,n)?==?True
void?siftdn(n)
?????i?=?1
?????loop:
?????????//?獲取理論上的左孩子下標
?????????c?=?2*i
?????????//?如果左孩子下標已經越界?
?????????//?說明當前已經是葉子結點
?????????if?c?>?n:
?????????????break;
?????????//如果存在右孩子?
?????????//?則獲取左右孩子中更小的一個
?????????//?和父結點比較
?????????if?c+1?<=?n:
?????????????if?a[c]?>?a[c+1]
?????????????????c++
?????????//?父結點小于等于左右孩子結點則停止
?????????if?a[i]?<=?a[c]
?????????????break;
?????????//?父結點比左右孩子結點大?
?????????//?則與其中較小的孩子結點交換
?????????//?也就是讓原來的孩子結點成為父結點
?????????swap(a[i],a[c])
?????????//?繼續(xù)向下循環(huán)
?????????i?=?c?????

siftdn調整過程演示

在頭部元素更新為21的調整過程如圖：

2.5 堆排序

場景：假如有200w數(shù)據，要找最大的前10個數(shù)。

分析：那么就需要先建立大小為10個元素的小頂堆，然后再逐漸把其他所有元素依次滲透進來比較或入堆淘汰老數(shù)據或跳過，直至所有數(shù)據滲透完成，最后小根堆的10個元素就是最大的10個數(shù)了。

小根堆：選擇最大的TopN個數(shù)據使用小根堆，因為堆頂就是最小的數(shù)據，每次進來的新數(shù)據只需要和堆頂比較即可，如果小于堆頂則跳過，如果大于堆頂則替換掉堆頂進行siftdn調整，來找到新進元素的正確位置，以及產生新的堆頂。

建堆過程：可以自頂向下自底向上均可，以下采用自底向上思路分析?？梢詫?shù)組的葉子節(jié)點，是單個結點滿足二叉堆的定義，于是從底層葉子結點的父結點從左到右，逐個向上構建二叉堆，直到第一個節(jié)點時整個數(shù)組就是一個二叉堆，這個過程是siftup和siftdn的混合，宏觀上來看是自底向上，微觀上每個父結點是自頂向下。

滲透排序過程：完成堆化之后，開處理N之后的元素，從N+1~200w，遇到比當前堆頂大的則與堆頂元素交換，進入堆觸發(fā)siftdn調整，直至生產新的小根堆。

代碼實戰(zhàn)：leetCode 第215題 數(shù)組中的第K個最大元素。

這道題可以用堆排序來完成，建立小根堆取堆頂元素即可，驗證通過的代碼舉例：

//leetcode?215th?the?Kth?Num
//Source?Code:C++
class?Solution?{
public:
????//調整以當前節(jié)點為根的子樹為小頂堆
????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++;
????????????}
????????????//當前父節(jié)點比左右孩子其中一個大
????????????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 堆小結

從實踐來看，堆的重要用途是堆排序，堆排序重點是初始化堆和調整堆兩個過程，然而這兩個過程都離不開siftup和siftdn兩個函數(shù)，因此掌握這兩個函數(shù)，基本上就掌握了堆。

由于堆是二叉樹，因此在實際使用中需要結合樹的遍歷和循環(huán)來實現(xiàn)堆調整，掌握堆調整過程和二叉樹遍歷過程，拿下堆，指日可待。

3 優(yōu)先隊列

先來看看維基百科對優(yōu)先隊列的定義：

優(yōu)先隊列是計算機科學中的一類抽象數(shù)據類型。?

優(yōu)先隊列中的每個元素都有各自的優(yōu)先級，優(yōu)先級最高的元素最先得到服務；優(yōu)先級相同的元素按照其在優(yōu)先隊列中的順序得到服務。

優(yōu)先隊列至少需要支持下述操作：

a.插入帶優(yōu)先級的元素?

b.取出具有最高優(yōu)先級的元素

c.查看最高優(yōu)先級的元素。

綜合考慮插入和刪除的性能 優(yōu)先隊列一般采用堆來實現(xiàn)。

由于優(yōu)先隊列的元素既可以是基礎類型，也可以是復合類型，因此在C++中一般使用模板來定義優(yōu)先隊列，從而提高其可擴展性，簡單定義：

template<class?T>
class?priqueue?{
public:
???????//構造函數(shù)?初始化
???????priqueue(int?maxsize);
???????//將T類型新元素添加到隊列中
???????void?insert(T?t);
???????//獲取隊列中最小的元素
???????T?extractmin();
};

3.1 優(yōu)先隊列的理論實現(xiàn)

實現(xiàn)優(yōu)先隊列的候選數(shù)據結構包括：有序序列、無序序列、堆。

• 有序序列
  有序序列中存儲的數(shù)據都是有序的，在執(zhí)行extractmin獲取最小值時復雜度O(1)，但是在添加新元素時就存在大量的移動和查找正確的位置最大復雜度O(N)，因此在insert和extactmin同時執(zhí)行N次時，最大復雜度為O(N^2)。

• 無序序列
  無序序列中存儲的元素是無序的，在執(zhí)行insert操作復雜度為O(1)，但是在extractmin時每次都要進行一次遍歷復雜度為O(N)，因此在insert和extractmin同時執(zhí)行N次時，最大復雜度為O(N^2)。

• 堆結構
  從上一節(jié)我們知道堆的insert不如無序序列那么隨意，extractmin也沒有有序序列那么容易，每次都需要進行siftup和siftdn操作進行調整，但是同時執(zhí)行insert和extractmin時，復雜度是O(nlogn)，優(yōu)于O(N^2)。

綜上可知，堆結構在實現(xiàn)優(yōu)先隊列的插入和刪除操作時復雜性都很穩(wěn)定，在大量數(shù)據的場景下優(yōu)于有序序列和無序序列，因此權衡之下選擇堆作為優(yōu)先隊列的底層數(shù)據結構。

3.2?優(yōu)先隊列的工程實現(xiàn)

考慮優(yōu)先隊列的靈活性和效率，可以基于模板化和堆來實現(xiàn)優(yōu)先隊列：

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ù)據
????????void?insert(T?t)
????????{?
????????????int?i,p;
????????????x[++n]?=?t;
????????????//末尾添加新數(shù)據?執(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--];
??????????//針對新堆頂進行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關于優(yōu)先隊列的實現(xiàn)，只是一部分簡潔的代碼，旨在表現(xiàn)insert和extract操作時如何運用堆的siftup和siftdn操作來封裝成優(yōu)先隊列類的基礎成員函數(shù)。?

3.3 優(yōu)先隊列的自定義優(yōu)先級

模板化的優(yōu)先隊列擴展了使用場景，但是也產生了新的問題，就是默認的優(yōu)先級比較函數(shù)不一定滿足所有要求，因此很多時候都需要自己來定義優(yōu)先級判定函數(shù)。

實現(xiàn)了一個模板優(yōu)先隊列需要三個參數(shù)：?

• 容器元素的類型

• 存儲數(shù)據所用的容器

• 比較函數(shù) 缺省情況是less

#include
//?隊列和優(yōu)先隊列的聲明
std::queue?pq;
std::priority_queuestd::vector,?cmp>?pq;
//模板化優(yōu)先隊列的主要參數(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)先隊列的應用

可以認為優(yōu)先隊列是對堆的工具化封裝，加上模板和自定義比較函數(shù)兩個利器加持，優(yōu)先隊列讓使用者不再苦于堆排序的原始造輪子。

TopN問題和優(yōu)先隊列

仍以LeetCode 215題為例，獲取數(shù)組第K大元素。

上一節(jié)中我們直接使用堆，但是構建的是小頂堆，并且大小是K個元素，遍歷完成之后直接取堆頂即可，但是在數(shù)據量不大或者內存足夠的情況下，可以直接建立優(yōu)先隊列。?

默認的優(yōu)先隊列本質上是大頂堆，那么堆頂就不是第K大元素了，但是從堆頂開始依次pop出K-1個元素，堆頂也就是第K大元素了。?

當然也可以修改比較函數(shù)實現(xiàn)小頂堆，取堆頂元素也是可以的，要靈活運用。使用優(yōu)先隊列實現(xiàn)LeetCode 第215題，代碼如下：

//默認的比較函數(shù)是less?也就是優(yōu)先隊列相當于最大堆
//堆頂元素為最大值
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)先隊列是貪心算法的重要組成部分，借助于優(yōu)先隊列貪心算法可以解決非常多的實際問題包括：

• 旅行商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