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

來自：后端技術(shù)指南針

1 前言

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

通過本文你將了解到以下內(nèi)容：

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

2 堆

2.1 堆的基本概念

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

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

堆是計算機科學(xué)中的一種特別的樹狀數(shù)據(jù)結(jié)構(gòu)。

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

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

2.2 堆的兩個特性

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

• 元素順序

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

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

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

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

如圖為小根堆結(jié)構(gòu)：

• 樹的形狀

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

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

2.3 堆的數(shù)組表示

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

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

//數(shù)組下標范圍
i<=n && i>=1
//根結(jié)點下標為1
root_index = 1
//層次遍歷第i個結(jié)點的值等于數(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個元素的父結(jié)點下標i/2
parent(i) = i/2

堆和數(shù)組的對應(yīng)關(guān)系如圖：

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é)點那么a[1...n]仍然滿足堆的特性，不需要調(diào)整；
B. 如果a[n]比它的父結(jié)點要小無法保證堆的特性，就需要進行調(diào)整；

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

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

siftup調(diào)整過程演示

在尾部插入元素16的調(diào)整過程如圖：

2.4.2 siftdn函數(shù)的原理

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

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

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

siftdn調(diào)整過程演示

在頭部元素更新為21的調(diào)整過程如圖：

2.5 堆排序

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

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

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

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

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

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

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

//leetcode 215th the Kth Num
//Source Code:C++
class Solution {
public:
    //調(diào)整以當(dāng)前節(jié)點為根的子樹為小頂堆
    int heapadjust(vector<int> &nums,int curindex,int len){
        int curvalue = nums[curindex];
        int child = curindex*2+1;
        while(child<len){
            //左右孩子中較小的那個
            if(child+1<len && nums[child] > nums[child+1]){
                child++;
            }
            //當(dāng)前父節(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()<k)
            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<len;j++){
            if(nums[j]<=subnums[0])
                continue;
            subnums[0] = nums[j];
            heapadjust(subnums,0,sublen);
        }
        return subnums[0];  
    }
};

2.6 堆小結(jié)

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

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

3 優(yōu)先隊列

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

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

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

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

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

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

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

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

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

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

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

實現(xiàn)優(yōu)先隊列的候選數(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時每次都要進行一次遍歷復(fù)雜度為O(N)，因此在insert和extractmin同時執(zhí)行N次時，最大復(fù)雜度為O(N^2)。

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

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

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ù)據(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--];
          //針對新堆頂進行siftdn操作
          for (i = 1; (c = 2*i) <= n; i = c) {
              if (c+1 <= n && x[c+1] < x[c])
                   c++;
              if (x[i] <= x[c])
                   break;
               swap(c,i);
          }
         return t;
      }
};

上述代碼摘自編程珠璣并不是STL關(guān)于優(yōu)先隊列的實現(xiàn)，只是一部分簡潔的代碼，旨在表現(xiàn)insert和extract操作時如何運用堆的siftup和siftdn操作來封裝成優(yōu)先隊列類的基礎(chǔ)成員函數(shù)。 

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

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

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

• 容器元素的類型

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

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

#include<quque>
// 隊列和優(yōu)先隊列的聲明
std::queue<T> pq;
std::priority_queue<T, std::vector<T>, cmp> pq;
//模板化優(yōu)先隊列的主要參數(shù)
priority_queue<Type, Container, Func>
//舉例
priority_queue<pair<char,int>,vector<pair<char,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īng)用

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

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

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

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

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

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

//默認的比較函數(shù)是less 也就是優(yōu)先隊列相當(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<k-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

特別推薦一個分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長按關(guān)注一下：
長按訂閱更多精彩▼
如有收獲，點個在看，誠摯感謝