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

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

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)，堆是一種二叉樹。

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

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

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

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

2.2 堆的兩個(gè)特性

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

• 元素順序

在堆中任何結(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)的相對(duì)大小和順序；

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

• 樹的形狀

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

上述的兩種性質(zhì)可以保證快捷找到最值，并且在插入和刪除新元素時(shí)可以實(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ù)組存儲(chǔ)的堆具備以下性質(zhì)：

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

2.4 堆的調(diào)整函數(shù)

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

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是一個(gè)不斷向上循環(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 = p

siftup調(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是一個(gè)不斷向下循環(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;
         //如果存在右孩子 
         // 則獲取左右孩子中更小的一個(gè)
         // 和父結(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 堆排序

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

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

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

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

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

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

這道題可以用堆排序來完成，建立小根堆取堆頂元素即可，驗(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<len){
            //左右孩子中較小的那個(gè)
            if(child+1<len && nums[child] > nums[child+1]){
                child++;
            }
            //當(dāng)前父節(jié)點(diǎn)比左右孩子其中一個(gè)大
            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個(gè)的小頂堆
        //截取數(shù)組的前k個(gè)元素
        vector<int> subnums(nums.begin(),nums.begin()+k);
        int len = nums.size();
        int sublen = subnums.size();
        //將數(shù)組的前k個(gè)元素建立小頂堆
        for(int i=sublen/2-1;i>=0;i--){
            heapadjust(subnums,i,sublen);
        }
        //建立好小頂堆之后 開始逐漸吸收剩余的數(shù)組元素
        //動(dòng)態(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é)

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

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

3 優(yōu)先隊(duì)列

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

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

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

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

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

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

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

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

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

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)包括：有序序列、無序序列、堆。

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

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

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

綜上可知，堆結(jié)構(gòu)在實(shí)現(xiàn)優(yōu)先隊(duì)列的插入和刪除操作時(shí)復(fù)雜性都很穩(wěn)定，在大量數(shù)據(jù)的場(chǎng)景下優(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--];
          //針對(duì)新堆頂進(jì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)先隊(duì)列的實(shí)現(xiàn)，只是一部分簡(jiǎn)潔的代碼，旨在表現(xiàn)insert和extract操作時(shí)如何運(yùn)用堆的siftup和siftdn操作來封裝成優(yōu)先隊(duì)列類的基礎(chǔ)成員函數(shù)。 

3.3 優(yōu)先隊(duì)列的自定義優(yōu)先級(jí)

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

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

• 容器元素的類型

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

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

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

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

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

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

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

默認(rèn)的優(yōu)先隊(duì)列本質(zhì)上是大頂堆，那么堆頂就不是第K大元素了，但是從堆頂開始依次pop出K-1個(gè)元素，堆頂也就是第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<k-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

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