说明
优先队列std::priority_queue 可用于构造堆。
比如：
大顶堆：priority_queue<int> q;，大的数在前边。
小顶堆： priority_queue<int, vector<int>, greater<int> > q;，小的数在前边。
std::priority_queue是个模板类，如下：
template<
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class priority_queue;
有3个模板参数，其中后两个都有默认值。第1个参数是数据类型，比如int。第2个参数是用于存储元素的底层容器类型，默认是用vector。第3个参数是比较函数，默认是less，所以默认是大顶堆，大的在前边。
第2个容器参数，vector和deque满足使用要求，如果是要自己编写的容器代码，则要求自己写的容器代码能最忌访问，且有如下接口：empty(); size(); front(); push_back(); pop_back()。日常使用，使用vector即可。
头文件
#include <queue>
基本操作
| 操作 | 说明 |
|---|---|
| top | 访问栈顶元素 |
| empty | 检查底层的容器是否为空 |
| size | 返回容纳的元素数 |
| push | 插入元素，并对底层容器排序 |
| pop | 删除栈顶元素 |
| swap | 两个priority queue交换内容 |
| emplace（c++11引入） | 原位构造元素并排序底层容器 |
其中emplace由c++11引入，功能与push一致，但是效率更高，原地构造，不涉及copy和move操作。
例子：大顶堆
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> pq;
pq.push(30);
pq.push(100);
pq.push(25);
pq.push(40);
// output
while (!pq.empty()) {
cout << pq.top() << "\t";
pq.pop();
}
cout << endl;
return 0;
}
结果如下：
100 40 30 25
例子：小顶堆
#include <iostream>
#include <queue>
#include <functional>
using namespace std;
int main()
{
priority_queue<int, vector<int>, greater<int> > pq;
pq.push(30);
pq.push(100);
pq.push(25);
pq.push(40);
// output
while (!pq.empty()) {
cout << pq.top() << "\t";
pq.pop();
}
cout << endl;
return 0;
}
结果如下：
25 30 40 100
例子：自定义排序函数
#include <iostream>
#include <queue>
using namespace std;
class A {
public:
A(int key1, int key2) : key1_(key1), key2_(key2) {}
bool operator<(const A& other) const {
return (key2_ < (other.key2_));
}
void print() const {
cout << key1_ << "\t" << key2_ << endl;
}
private:
int key1_;
int key2_;
};
int main()
{
priority_queue<A> pq;
pq.emplace(25, 26);
pq.emplace(100, 7);
pq.emplace(30, 63);
pq.emplace(40, 6);
// output
while (!pq.empty()) {
pq.top().print();
pq.pop();
}
cout << endl;
return 0;
}
结果如下：
30 63
25 26
100 7
40 6
通过operator<自定义排序函数，按照key2_从大到小排序。
其中使用了emplace，也可换成pq.push(A(25, 26));。
参考
http://www.cplusplus.com/reference/queue/priority_queue/
https://zh.cppreference.com/w/cpp/container/priority_queue
网友评论