admin管理员组文章数量:1623800
priority_queue的用法(原博客)
1.1 简介
priority_queue本质是一个堆。1. 头文件是#include<queue>
2. 关于priority_queue中元素的比较
模板申明带3个参数:**priority_queue<Type, Container, Functional>**,其中Type 为数据类型,Container为保存数据的容器,Functional 为元素比较方式。
Container必须是用数组实现的容器,比如vector,deque等等,但不能用 list。STL里面默认用的是vector。
常用的操作如下:
empty() 如果优先队列为空,则返回真
pop() 删除第一个元素
push() 加入一个元素
size() 返回优先队列中拥有的元素的个数
top() 返回优先队列中有最高优先级的元素
2.2 默认比较方式
比较方式默认用operator<,所以如果把后面2个参数缺省的话,优先队列就是大顶堆(降序),队头元素最大。特别注意pair的比较函数。以下代码返回一个降序输出:
#include <iostream> #include <queue> using namespace std; int main(){ priority_queue<int> q; for( int i= 0; i< 10; ++i ) q.push(i); while( !q.empty() ){ cout<<q.top()<<endl; q.pop(); } return 0; }
以下代代码返回pair的比较结果,先按照pair的first元素降序,first元素相等时,再按照second元素降序:
#include<iostream> #include<vector> #include<queue> using namespace std; int main(){ priority_queue<pair<int,int> > coll; pair<int,int> a(3,4); pair<int,int> b(3,5); pair<int,int> c(4,3); coll.push(c); coll.push(b); coll.push(a); while(!coll.empty()) { cout<<coll.top().first<<"\t"<<coll.top().second<<endl; coll.pop(); } return 0; }
2.2 小顶堆的构建
如果要用到小顶堆,则一般要把模板的3个参数都带进去。STL里面定义了一个仿函数greater<>,基本类型可以用这个仿函数声明小顶堆。
以下代码返回一个升序输出:
#include <iostream> #include <queue> using namespace std; int main(){ priority_queue<int, vector<int>, greater<int> > q; for( int i= 0; i< 10; ++i ) q.push(10-i); while( !q.empty() ){ cout << q.top() << endl; q.pop(); } return 0; }
以下代代码返回pair的比较结果,先按照pair的first元素升序,first元素相等时,再按照second元素升序:
#include<iostream> #include<vector> #include<queue> using namespace std; int main(){ priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > coll; pair<int,int> a(3,4); pair<int,int> b(3,5); pair<int,int> c(4,3); coll.push(c); coll.push(b); coll.push(a); while(!coll.empty()) { cout<<coll.top().first<<"\t"<<coll.top().second<<endl; coll.pop(); } return 0; }
2.3 自定义类型
对于自定义类型,则必须重载operator<或者重写仿函数。
2.3.1 重载operator<的例子
返回true时,说明左边形参的优先级低于右边形参。
#include <iostream> #include <queue> using namespace std; struct Node{ int x, y; Node(int a=0, int b=0): x(a),y(b){} }; bool operator<(Node a, Node b){//返回true时,说明a的优先级低于b //x值较大的Node优先级低(x小的Node排在队前) //x相等时,y大的优先级低(y小的Node排在队前) if( a.x== b.x ) return a.y> b.y; return a.x> b.x; } int main(){ priority_queue<Node> q; for( int i= 0; i< 10; ++i ) q.push( Node( rand(), rand() ) ); while( !q.empty() ){ cout << q.top().x << ' ' << q.top().y << endl; q.pop(); } return 0; }
自定义类型重载operator<后,声明对象时就可以只带一个模板参数。
但此时不能像基本类型这样声明priority_queue<Node,vector<Node>,greater<Node> >,原因是greater<Node>没有定义,如果想用这种方法定义则可以重载operator >。
例子:返回的是小顶堆。但不怎么用,习惯是重载operator<。
#include <iostream> #include <queue> using namespace std; struct Node{ int x, y; Node( int a= 0, int b= 0 ): x(a), y(b) {} }; bool operator>( Node a, Node b ){//返回true,a的优先级大于b //x大的排在队前部;x相同时,y大的排在队前部 if( a.x== b.x ) return a.y> b.y; return a.x> b.x; } int main(){ priority_queue<Node,vector<Node>,greater<Node> > q; for( int i= 0; i< 10; ++i ) q.push( Node( rand(), rand() ) ); while( !q.empty() ){ cout << q.top().x << ' ' << q.top().y << endl; q.pop(); } return 0; }
2.3.2 重写仿函数的例子(返回值排序与2.3.1相同,都是小顶堆。先按x升序,x相等时,再按y升序):
#include <iostream> #include <queue> 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 ){//默认是less函数 //返回true时,a的优先级低于b的优先级(a排在b的后面) if( a.x== b.x ) return a.y> b.y; return a.x> b.x; } }; int main(){ priority_queue<Node, vector<Node>, cmp> q; for( int i= 0; i< 10; ++i ) q.push( Node( rand(), rand() ) ); while( !q.empty() ){ cout << q.top().x << ' ' << q.top().y << endl; q.pop(); } return 0; }
本文标签: Priority
版权声明:本文标题:priority的用法 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728896029a1178417.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论