admin管理员组文章数量:1623789
引言
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
是从小到大,一定不要弄混!!!!
本文标签: 队列stlpriorityqueue
版权声明:本文标题:STL中的priority_queue(优先队列) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728897157a1178559.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论