C++中优先级队列（priority_queue）详解

在刷题过程中，我们会遇到求第K大元素这样的问题，其中一种效率还可以的做法是使用优先级队列实现，底层数据结构一般是堆。我估计很多同学搞不清楚优先级队列和堆的区别，不服的举手，这个问题我们最后讨论，我们先来仔细看看C++标准库中priority_queue的用法，这是本文的重点。

优先级队列操作

priority_queue这个类在STL的queue文件中，有如下方法：

首先是top函数，这个函数返回堆顶的元素，大堆返回最大的元素，小堆返回最小的元素。

其次是大小接口，empty函数是检查容器是否为空，size返回元素的个数。

然后最重要的是修改操作，push函数可以插入元素到队列中，emplace函数也是插入，这2个有啥区别呢？注意C++11的容器操作很多都加了emplace相关的函数，这个函数更加高效，可以减少拷贝，一般情况下优先使用emplace函数，性能和内存都会好些。

修改操作pop就是将堆顶元素删除掉。

swap是干什么的？

swap操作有点特别，如下例子：

// priority_queue::swap
#include <iostream>       // std::cout
#include <queue>          // std::priority_queue

int main ()
{
  std::priority_queue<int> foo,bar;
  foo.push (15); foo.push(30); foo.push(10);
  bar.push (101); bar.push(202);

  foo.swap(bar);

  std::cout << "size of foo: " << foo.size() << '\n';
  std::cout << "size of bar: " << bar.size() << '\n';

  return 0;
}

这个例子会输出：

size of foo: 2
size of bar: 3

也即是说，swap是交换两个容器的数据，这种操作一般可以在外部自己实现，标准库提供了这个接口看了是考虑性能。

构造函数 - 比较参数

优先级队列的功能就这些，下面我们来看看构造函数：

auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);

模板有3个参数，第一个参数是类型，第二个参数是底层放数据的容器类型，第三个参数是比较函数，上面是将cmp这个参数传进去作为比较函数。

基本上就这些内容，如何实现求第K大的树呢？我们只需要让这个队列一直保留K个元素，堆顶的元素就是第K大的。

区别

下面我们来讨论一下优先级队列和堆的区别。

堆是一种数据结构，是一种非常确定的数据结构，堆顶是最值，就像链表、队列、栈这种数据结构。

而优先级队列是一种抽象的数据类型，只给了是什么的解释(what)，没有给具体实现(how)，只不过恰巧优先级队列大部分情况都是用堆实现的。