面试必知必会：堆和优先队列

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

• 优先队列的概念

• 优先队列的实现

• 优先队列的应用

1.优先队列的概念

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

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

2.优先队列的实现

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

• 有序序列

有序序列中存储的数据都是有序的， 在执行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)。

• 复杂度对照

在 数据量超过较大时O(N^2)的执行时间要比O(nlogn)大非常多 ，有兴趣可以试试，引用参考4中的数据曲线：

• 小结

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

3.优先队列的实现

• 基于模板化和堆的优先队列的简单实现

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操作 来封装成优先队列类的基础成员函数。

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

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

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

• 容器元素的类型

• 存储数据所用的容器

• 比较函数 缺省情况是less<T>

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

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<k-1;i++) 
      q.pop();
  return q.top();
}

• 优先队列和贪心算法

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

• 旅行商TSP问题

• 01背包问题

• 霍夫曼编码问题

• 最短路径 Dijkstra算法

• 最小生成树Prim算法

5.参考资料

• 《编程珠玑》

• http://www.laicar.com/book/echapter/5cb0a77e739207662ac8710c/links/item10/OEBPS/Text/part0009.xhtml

• 维基百科

• https://my.oschina.net/u/1246663/blog/227115

6.往期精彩

二叉树及其四大遍历