STL中的priority_queue（优先队列）

引言

priority_queue 也是一种队列，queue 有的性质和操作它也有（但是没有back操作了），唯一不同就是它可以自动排序；
它的本质是通过堆实现的，在堆排序中会见到它，下面说一下它的用法；

基本内容

头文件#include<queue>
定义priority_queue<Type, Container, Functional>
Type就是该队列的数据类型， Container是保存数据的容器类型，且该容器必须由数组实现的，默认情况是vector；Functional可以简单理解为数据的比较方法；

---

默认情况下只需要传入数据类型就可以，容器类型默认为 vector， 数据的比较方法默认为大顶堆（即从大到小排列）
如priority_queue<int> q1; 等价于 priority_queue<int, vector<int>, less<int>> q2;

注：这里面数据比较方法用到了仿函数less<int>，不了解仿函数的可以看看这篇文章：内建函数对象（STL）
不使用仿函数还可以自己写比较规则，只需要重载运算符 < 就可以了（比较方式默认用operator<），这里就不提了；

大顶堆

大顶堆可以理解为优先输出大的数据，也是priority_queue的默认情况；
这里的Functional是less<int>了；
测试代码：

#include<iostream> #include<vector> #include<queue> using namespace std;int main() {//默认情况priority_queue<int> q1;q1.push(1);q1.push(4);q1.push(3);q1.push(5);q1.push(2);q1.push(8); while (!q1.empty()) {cout << q1.top() << " ";q1.pop();}cout << endl;//下列和默认情况等价priority_queue<int, vector<int>, less<int>> q2;q2.push(1);q2.push(4);q2.push(3);q2.push(5);q2.push(2);q2.push(8); while (!q2.empty()) {cout << q2.top() << " ";q2.pop();}cout << endl;return 0; }

压入队列的数为：1 4 3 5 2 8
输出结果：

可以看出是从大到小排列的；

小顶堆

小顶堆可以理解为优先输出小的数据；
所以这里面Functional就需要用greater<int>了；
测试代码：

#include<iostream> #include<vector> #include<queue> using namespace std;int main() {priority_queue<int, vector<int>, greater<int>> q1;q1.push(1);q1.push(4);q1.push(3);q1.push(5);q1.push(2);q1.push(8);while (!q1.empty()) {cout << q1.top() << " ";q1.pop();}cout << endl;return 0; }

压入队列的数为：1 4 3 5 2 8
输出结果：

可以看出是从小到大排列的；

总结

再次声明以下使用priority_queue的几点：

• priority_queue没有back()操作
• priority_queue参数容器类型是由数组实现的
• 默认priority_queue是大顶堆（从大到小）
• less是从大到小，greater是从小到大，一定不要弄混！！！！

总结

以上是生活随笔为你收集整理的STL中的priority_queue（优先队列）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。