形象化描述:可以插队的队列。
头文件:<queue>
定义方法:较为简单的常见优先队列可直接定义;
如:priority_queue<int,vector<int>,greater<int> >pq;
即定义一个越小的整数优先级越大的优先队列。
若想实现自定义排序,需重载运算符()
如:
struct cmp {bool operator() (const int a,const int b) const true{return a%10 > b%10; //即个位数大的优先级高}};
定义方法:priority_queue<int,vector<int>,cmp> pq;
注意:优先队列使用top()获得队首元素。
常用操作速览:
q.size();//返回q里元素个数
q.empty();//返回q是否为空,空则返回1,否则返回0
q.push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素
q.back();//返回q的末尾元素
请注意:
priority_queue <node> q;
//node是一个结构体
//结构体里重载了‘<’小于符号
priority_queue <int,vector<int>,greater<int> > q;
//不需要#include<vector>头文件
//注意后面两个“>”不要写在一起,“>>”是右移运算符
priority_queue <int,vector<int>,less<int> >q;
例题:丑数(Uva 136)P120
形如:1,2,3,4,5,6,8,9,10,12,15等不能被除2,3,5以外的数整除的数,求第1500个丑数。
代码:
#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
const int coeff[3]={2,3,5};int main() {priority_queue<ll,vector<ll>,greater<ll> > pq;set<ll>s;pq.push(1);s.insert(1);for(int i=1;;i++) {ll x =pq.top();pq.pop();if(i==1500) {cout<<x<<endl;break;}for(int j=0;j<3;j++) {ll x2=x*coeff[j];//依次生成丑数if(!s.count(x2)) {//除重s.insert(x2);pq.push(x2);}}}
}