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

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

• 优先队列的概念

• 优先队列的实现

• 优先队列的应用

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.往期精彩

二叉树及其四大遍历