std：priority_queue
priority_queue允许用户为队列中元素设置优先级，放置元素的时候不是直接放到队尾，而是放置到比它优先级低的元素前面，标准库默认使用<操作符来确定优先级关系。
priority_queue模板类有三个模板参数：元素类型，容器类型，比较算子。其中后两个可以省略，默认容器为vector，默认算子为less，即如果x<y判断为真，则y排到x前面，y先出队。
定义priority_queue对象的示例代码如下：
priority_queue<int> q1;
priority_queue<pair<int,int>> q2;
priority_queue<int,vector<int>,greater<int>> q3;//定义优先级小的先出队
priority_queue与queue的基本操作均相同，在使用q.top()时返回最高优先级的元素，该操作只适用于优先级队列。
如果要自己定义比较算子，可以有多种方法，最常见的就是重载比较运算符，注意重载操作返回的结果是bool类型，并且此处的比较操作与map等其他处不同，在map中以<作为比较操作，则值小的排在前面，而优先级队列中以<作为比较操作，来确定优先级关系，此处表明优先级关系为按值从小到大排列，值大的优先级高，而优先级高的放在队列前面，反之以>操作符确定优先级关系时，表明优先级是按值从大到小排列，值小的优先级高，优先级高的放在队列前面。
下面代码创建一个简单的优先级队列，默认按照less确定优先级，即<操作符，先使用top返回最高优先级元素，然后使用pop删除队首元素，然后再返回最高优先级元素top，可以看出top由9变为5，表明最高优先级的排在队首：
#include <iostream>
#include <queue>
using namespace std;
int main ()
{
priority_queue<int> q;
q.push(1);
q.push(5);
q.push(3);
q.push(9);
q.push(2);
cout<<q.top()<<endl;
q.pop();
cout<<q.top()<<endl;
system("pause");
return 0;
}
下面这个例子是在priority_queue中插入(x,y,z)为一个元素的值，并且定义比较其中的z值来确定优先级顺序，z值大的排在队列前面
#include<iostream>
#include<queue>
#include<stdlib.h>
using namespace std;
class T
{
public:
int x,y,z;
T(int a,int b,int c):x(a),y(b),z(c)
{
}
};
bool operator<(const T&t1,const T&t2)
{
return t1.z<t2.z;
}
int main(void)
{
priority_queue<T>q;
q.push(T(4,4,3));
q.push(T(2,2,5));
q.push(T(1,5,4));
q.push(T(3,3,6));
while(!q.empty())
{
T t=q.top();
q.pop();
cout<<t.x<<" "<<t.y<<" "<<t.z<<endl;
}
system("Pause");
return 1;
本文内容参考自
STL系列之五 priority_queue 优先级队列 以及
c++queue容器介绍
priority_queue默认是大根堆，也就是大的元素会放在前面
例如
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int>q;
int a[15]={0,1,4,2,3,5};
const int n=5;
int main()
{
for(int i=1;i<=n;i++) q.push(a[i]);
while(q.size()!=0)
printf("%d ",q.top()),q.pop();
return 0;
}
它的输出结果是
那如何让priority_queue支持小根堆呢？:question:
回到顶部
方法一
将所有的数全部取负
这样的话绝对值小的数会变大，绝对值大的数会变小
这样就能实现小根堆了
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int>q;
int a[15]={0,1,4,2,3,5};
const int n=5;
int main()
{
for(int i=1;i<=n;i++) q.push(-a[i]);
while(q.size()!=0)
printf("%d ",-q.top()),q.pop();
return 0;
}
回到顶部
方法二
利用STL中自带的小根堆，很简单，只要在定义的时候写成
就好
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;//这样就可以实现小根堆了
int a[15]={0,1,4,2,3,5};
const int n=5;
int main()
{
for(int i=1;i<=n;i++) q.push(a[i]);
while(q.size()!=0)
printf("%d ",q.top()),q.pop();
return 0;
}
回到顶部
另外
priority_queue是支持自定义比较函数的
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int n=5;
struct node
{
int x,y;
node(){x=y=0;}
node(int a,int b){x=a;y=b;}
};
priority_queue<node>q;
bool operator<(const node &a,const node &b)
{
if(a.x!=b.x)return a.x>b.x;
return a.y<b.y;
}
int a[15]={0,1,4,4,3,5};
int b[15]={0,2,1,2,3,4};
int main()
{
for(int i=1;i<=n;i++) q.push(node(a[i],b[i]));
while(q.size()!=0)
printf("%d %d\n",q.top().x,q.top().y),q.pop();
return 0;
}
注意：priority_queue自定义函数的比较与sort正好是相反的，也就是说，如果你是把大于号作为第一关键字的比较方式，那么堆顶的元素就是第一关键字最小的
还可以这么写
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int n=5;
struct node
{
int x,y;
node(){x=y=0;}
node(int a,int b){x=a;y=b;}
bool operator <(const node &a)const
{
if(a.x!=x) return a.x<x;
return a.y>y;
}
};
priority_queue<node>q;
int a[15]={0,1,4,4,3,5};
int b[15]={0,2,1,2,3,4};
int main()
{
for(int i=1;i<=n;i++) q.push(node(a[i],b[i]));
while(q.size()!=0)
printf("%d %d\n",q.top().x,q.top().y),q.pop();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,m;
priority_queue<int,vector<int>,greater<int> > p;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int opt,x;
cin>>opt;
if(opt==1)
{
cin>>x;
p.push(x);
}
else if(opt==2)
{
cout<<p.top() <<endl;
}
else p.pop() ;
}
return 0;
}