admin管理员组文章数量:1623796
C++ 优先队列priority_queue
参考博客
优先队列
- 优先级队列是一个拥有权值观念的queue。它允许在底端添加元素、在顶端去除元素、删除元素。
- 缺省情况下,优先级队列利用一个大顶堆完成。STL堆详解与编程实现
头文件&定义
#include <queue>
#include <functional> //greater<>
// 定义
priority_queue<int> pq;
默认优先输出大数据
priority_queue<Type, Container, Functional>
其中,
Type
为数据类型.Container
为保存数据的容器.Functional
为元素比较的方式.若不写后面两个参数.
容器 默认使用
vector
比较方式 默认使用
operator <
即优先队列是大顶堆. 队头元素最大.
举例
srand(time(NULL));
priority_queue<int> pq1; // 默认是最大堆...
std::cout << "start..." << endl;
for (int i = 0; i < 10; i++) {
int t = rand() % 100;
cout << t << ends;
pq1.push(t);
}
std::cout << endl;
while (!pq1.empty())
{
cout << pq1.top() << ends;
pq1.pop();
}
cout << endl;
结果:
优先输出小数据 即小顶堆
priority_queue<int, vector<int>, greater<int> > p;
- 使用
greater<int>
. 即改用operator >
举例
priority_queue<int, vector<int>, greater<int>> pq2; // 最小堆
std::cout << "start..." << endl;
for (int i = 0; i < 10; i++) {
int t = rand() % 100;
std::cout << t << ends;
pq2.push(t);
}
std::cout << endl;
while (!pq2.empty())
{
cout << pq2.top() << ends;
pq2.pop();
}
cout << endl;
结果:
自定义优先级 重载默认的 < 符号
1. 使用 funtion .
// 定义比较函数
// 后面一个表示栈顶元素? 所以这个是 "最小堆"
bool myCom(int a, int b) {
return a % 10 > b % 10;
}
// 使用
priority_queue<int, vector<int>, function<bool(int,int)>> pq3(myCom);
std::cout << "start..." << endl;
for (int i = 0; i < 10; i++) {
int t = rand() % 100;
std::cout << t << ends;
pq3.push(t);
}
std::cout << endl;
while (!pq3.empty())
{
cout << pq3.top() << ends;
pq3.pop();
}
cout << endl;
输出结果:
2. 自定义数据类型
#include<iostream>
#include<queue>
#include<cstdlib>
using namespace std;
struct Node{
int x,y;
Node(int a=0, int b=0):
x(a), y(b) {}
};
struct cmp{
bool operator()(Node a, Node b){
if(a.x == b.x) return a.y>b.y;
return a.x>b.x;
}
};
int main(){
priority_queue<Node, vector<Node>, cmp>p;
for(int i=0; i<10; ++i)
p.push(Node(rand(), rand()));
while(!p.empty()){
cout<<p.top().x<<' '<<p.top().y<<endl;
p.pop();
}//while
//getchar();
return 0;
本文标签: 队列priorityqueue
版权声明:本文标题:C++ 优先队列priority_queue 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728897680a1178622.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论