当前位置: 代码迷 >> 综合 >> 数据结构 优先队列
  详细解决方案

数据结构 优先队列

热度:87   发布时间:2024-01-18 18:51:01.0

形象化描述:可以插队的队列。

头文件:<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);}}}
}