理解堆和优先队列

1 前言

今天一起学习一下堆和优先队列，重点是堆排序的理解和优先队列的用法。

通过本文你将了解到以下内容：

• 堆的基本原理
• 堆的调整函数
• 堆排序及其应用
• 优先队列的概念
• 优先队列的原理和应用

2 堆

2.1 堆的基本概念

数据结构中的堆区别于内存分配的堆，我们说的用于排序的堆是一种表示元素集合的结构，堆是一种二叉树。

看看维基百科中对于堆的定义和说明：

堆是计算机科学中的一种特别的树状数据结构。

堆始于J. W. J. Williams在1964年发表的堆排序，当时他提出了二叉堆树作为此算法的数据结构，堆在戴克斯特拉算法和带优先级队列中亦为重要的关键。

若是满足以下特性，即可称为堆：给定堆中任意节点P和C，若P是C的母节点，那么P的值会小于等于C的值。若母节点的值恒小于等于子节点的值，此堆称为最小堆；反之称为最大堆。

2.2 堆的两个特性

堆有两个决定性特性：元素顺序和树的形状

• 元素顺序

在堆中任何结点与其子结点的大小都遵守数值大小关系。

A. 如果结点大于等于其所有子结点，也就是堆的根是所有元素中最大的，这种堆称为大根堆(大顶堆、最大堆)；

B. 如果结点小于等于其所有子结点，也就是堆的根是所有元素中最小的，这种堆称为小根堆(小顶堆、最小堆)；

C. 大根堆/小根堆只是约定了父结点和子结点的大小关系，但是并不约束子结点的相对大小和顺序；

如图为小根堆结构：

• 树的形状

堆这种二叉树最多在两层具有叶子结点，并且最底层的叶子结点靠左分布，该树种不存在空闲位置，也就是堆是个完全二叉树。

上述的两种性质可以保证快捷找到最值，并且在插入和删除新元素时可以实现重新组织再次满足堆的性质。

2.3 堆的数组表示

堆中没有空闲位置并且数组是连续的，但是数组的下标是从0开始，为了统一，我们统一从1开始，也就是root结点的数组index=1，那么可以通过数组的index可以通过父结点找到左右子结点，也可以通过子结点找到父结点。

数组的元素遍历就是堆的层次遍历的结果，因此数组存储的堆具备以下性质：

//数组下标范围
i<=n && i>=1
//根结点下标为1
root_index = 1
//层次遍历第i个结点的值等于数组第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

堆和数组的对应关系如图：

2.4 堆的调整函数

堆调整的过程非常像数学归纳法的递推过程，看一下就知道，敲黑板！以下两个函数对于掌握堆非常重要。

2.4.1 siftup函数的原理

以小根堆为例，之前a[1...n-1]满足堆的特性，在数组a[n]插入新元素之后，就产生了两种情况：
A. 如果a[n]大于父结点那么a[1...n]仍然满足堆的特性，不需要调整；
B. 如果a[n]比它的父结点要小无法保证堆的特性，就需要进行调整；

循环过程：自底向上的调整过程就是新加入元素不断向上比较置换的过程，直到新结点的值大于其父结点，或者新结点成为根结点为止。
停止条件：siftup是一个不断向上循环比较置换的过程，理解循环的关键是循环停止的条件，从伪码中可以清晰地看到，siftup的伪码：

//siftup运行的前置条件
heap(1,n-1) == True
void siftup(n)
     i = n
     loop:
         // 循环停止条件一
         // 已经是根结点
         if i == 1:
             break;
         p = i/2
         // 循环停止条件二
         // 调整结点大于等于在此位置的父结点
         if a[p] <= a[i]
              break;
         swap(a[p],a[i])
         // 继续向上循环
         i = p

siftup调整过程演示

在尾部插入元素16的调整过程如图：

2.4.2 siftdn函数的原理

以小根堆为例，之前a[1...n]满足堆的特性，在数组a[1]更新元素之后，就产生了两种情况：
A. 如果a[1]小于等于子结点仍然满足堆的特性，不需要调整；
B. 如果a[1]大于子结点无法保证堆的特性，就需要进行调整；

循环过程：自顶向下的调整过程就是新加入元素不断向下比较置换的过程，直到新结点的值小于等于其子结点，或者新结点成为叶结点为止。
停止条件：siftdn是一个不断向下循环比较置换的过程，理解循环的关键是循环停止的条件，从伪码中可以清晰地看到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])
         // 继续向下循环
         i = c     

siftdn调整过程演示

在头部元素更新为21的调整过程如图：

2.5 堆排序

场景：假如有200w数据，要找最大的前10个数。

分析：那么就需要先建立大小为10个元素的小顶堆，然后再逐渐把其他所有元素依次渗透进来比较或入堆淘汰老数据或跳过，直至所有数据渗透完成，最后小根堆的10个元素就是最大的10个数了。

小根堆：选择最大的TopN个数据使用小根堆，因为堆顶就是最小的数据，每次进来的新数据只需要和堆顶比较即可，如果小于堆顶则跳过，如果大于堆顶则替换掉堆顶进行siftdn调整，来找到新进元素的正确位置，以及产生新的堆顶。

建堆过程：可以自顶向下自底向上均可，以下采用自底向上思路分析。可以将数组的叶子节点，是单个结点满足二叉堆的定义，于是从底层叶子结点的父结点从左到右，逐个向上构建二叉堆，直到第一个节点时整个数组就是一个二叉堆，这个过程是siftup和siftdn的混合，宏观上来看是自底向上，微观上每个父结点是自顶向下。

渗透排序过程：完成堆化之后，开处理N之后的元素，从N+1~200w，遇到比当前堆顶大的则与堆顶元素交换，进入堆触发siftdn调整，直至生产新的小根堆。

代码实战：leetCode 第215题 数组中的第K个最大元素。

这道题可以用堆排序来完成，建立小根堆取堆顶元素即可，验证通过的代码举例：

//leetcode 215th the Kth Num
//Source Code:C++
class Solution {
public:
    //调整以当前节点为根的子树为小顶堆
    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++;
            }
            //当前父节点比左右孩子其中一个大
            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个的小顶堆
        //截取数组的前k个元素
        vector<int> subnums(nums.begin(),nums.begin()+k);
        int len = nums.size();
        int sublen = subnums.size();
        //将数组的前k个元素建立小顶堆
        for(int i=sublen/2-1;i>=0;i--){
            heapadjust(subnums,i,sublen);
        }
        //建立好小顶堆之后 开始逐渐吸收剩余的数组元素
        //动态与堆顶元素比较 替换
        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两个函数，因此掌握这两个函数，基本上就掌握了堆。

由于堆是二叉树，因此在实际使用中需要结合树的遍历和循环来实现堆调整，掌握堆调整过程和二叉树遍历过程，拿下堆，指日可待。

3 优先队列

先来看看维基百科对优先队列的定义：

优先队列是计算机科学中的一类抽象数据类型。 

优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。

优先队列至少需要支持下述操作：

a.插入带优先级的元素 

b.取出具有最高优先级的元素

c.查看最高优先级的元素。

综合考虑插入和删除的性能 优先队列一般采用堆来实现。

由于优先队列的元素既可以是基础类型，也可以是复合类型，因此在C++中一般使用模板来定义优先队列，从而提高其可扩展性，简单定义：

template<class T>
class priqueue {
public:
       //构造函数 初始化
       priqueue(int maxsize);
       //将T类型新元素添加到队列中
       void insert(T t);
       //获取队列中最小的元素
       T extractmin();
};

3.1 优先队列的理论实现

实现优先队列的候选数据结构包括：有序序列、无序序列、堆。

• 有序序列
  有序序列中存储的数据都是有序的，在执行extractmin获取最小值时复杂度O(1)，但是在添加新元素时就存在大量的移动和查找正确的位置最大复杂度O(N)，因此在insert和extactmin同时执行N次时，最大复杂度为O(N^2)。

• 无序序列
  无序序列中存储的元素是无序的，在执行insert操作复杂度为O(1)，但是在extractmin时每次都要进行一次遍历复杂度为O(N)，因此在insert和extractmin同时执行N次时，最大复杂度为O(N^2)。

• 堆结构
  从上一节我们知道堆的insert不如无序序列那么随意，extractmin也没有有序序列那么容易，每次都需要进行siftup和siftdn操作进行调整，但是同时执行insert和extractmin时，复杂度是O(nlogn)，优于O(N^2)。

综上可知，堆结构在实现优先队列的插入和删除操作时复杂性都很稳定，在大量数据的场景下优于有序序列和无序序列，因此权衡之下选择堆作为优先队列的底层数据结构。

3.2 优先队列的工程实现

考虑优先队列的灵活性和效率，可以基于模板化和堆来实现优先队列：

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;
        }
        //插入新数据
        void insert(T t)
        { 
            int i,p;
            x[++n] = t;
            //末尾添加新数据 执行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关于优先队列的实现，只是一部分简洁的代码，旨在表现insert和extract操作时如何运用堆的siftup和siftdn操作来封装成优先队列类的基础成员函数。 

3.3 优先队列的自定义优先级

模板化的优先队列扩展了使用场景，但是也产生了新的问题，就是默认的优先级比较函数不一定满足所有要求，因此很多时候都需要自己来定义优先级判定函数。

实现了一个模板优先队列需要三个参数： 

• 容器元素的类型

• 存储数据所用的容器

• 比较函数 缺省情况是less

#include
// 队列和优先队列的声明
std::queue pq;
std::priority_queuestd::vector, cmp> pq;
//模板化优先队列的主要参数
priority_queue
//举例
priority_queuechar,int>,vectorchar,int>>,compare> pq;
//自定义比较函数
struct compare
{
    bool operator()(const pair<char,int> a,const pair<char,int> b){
        return b.second > a.second;
    }  
};

3.4 优先队列的应用

可以认为优先队列是对堆的工具化封装，加上模板和自定义比较函数两个利器加持，优先队列让使用者不再苦于堆排序的原始造轮子。

TopN问题和优先队列

仍以LeetCode 215题为例，获取数组第K大元素。

上一节中我们直接使用堆，但是构建的是小顶堆，并且大小是K个元素，遍历完成之后直接取堆顶即可，但是在数据量不大或者内存足够的情况下，可以直接建立优先队列。 

默认的优先队列本质上是大顶堆，那么堆顶就不是第K大元素了，但是从堆顶开始依次pop出K-1个元素，堆顶也就是第K大元素了。 

当然也可以修改比较函数实现小顶堆，取堆顶元素也是可以的，要灵活运用。使用优先队列实现LeetCode 第215题，代码如下：

//默认的比较函数是less 也就是优先队列相当于最大堆
//堆顶元素为最大值
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();
}

优先队列是贪心算法的重要组成部分，借助于优先队列贪心算法可以解决非常多的实际问题包括：

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