priority_queue的用法

更新时间:2023-05-20 13:43:33 阅读: 评论:0

priority_queue的⽤法
priority_queue本质是⼀个堆。
1. 头⽂件是#include<queue>
2. 关于priority_queue中元素的⽐较
  模板申明带3个参数:priority_queue<Type, Container, Functional>,其中Type 为数据类型,Container为保存数据的容器,Functional 为元素⽐较⽅式。
  Container必须是⽤数组实现的容器,⽐如vector,deque等等,但不能⽤ list。STL⾥⾯默认⽤的是vector。
2.1 ⽐较⽅式默认⽤operator<,所以如果把后⾯2个参数缺省的话,优先队列就是⼤顶堆(降序),队头元素最⼤。特别注意pair的⽐较函数。
  以下代码返回⼀个降序输出:
1 #include <iostream>
2 #include <queue>
3using namespace std;
4int main(){
5    priority_queue<int> q;
6for( int i= 0; i< 10; ++i ) q.push(i);
7while( !q.empty() ){
8        cout<&p()<<endl;
9        q.pop();
10    }
11return0;
12 }
  以下代代码返回pair的⽐较结果,先按照pair的first元素降序,first元素相等时,再按照cond元素降序:
1 #include<iostream>
2 #include<vector>
3 #include<queue>
4using namespace std;
5int main(){英文合同范本
6    priority_queue<pair<int,int> > coll;
7    pair<int,int> a(3,4);
8    pair<int,int> b(3,5);
9    pair<int,int> c(4,3);
10    coll.push(c);
11    coll.push(b);
12    coll.push(a);
13while(!pty())
14    {
15        cout<&p().first<<"\t"<&p().cond<<endl;
16        coll.pop();
17    }
18return0;
19 }
2.2 如果要⽤到⼩顶堆,则⼀般要把模板的3个参数都带进去。STL⾥⾯定义了⼀个仿函数greater<>,基本类型可以⽤这个仿函数声明⼩顶堆。
  以下代码返回⼀个升序输出:
1 #include <iostream>
2 #include <queue>
3using namespace std;
4int main(){
5    priority_queue<int, vector<int>, greater<int> > q;
6for( int i= 0; i< 10; ++i ) q.push(10-i);
7while( !q.empty() ){
8        cout << q.top() << endl;
9        q.pop();
10    }
11return0;
色彩的搭配
12 }
  以下代代码返回pair的⽐较结果,先按照pair的first元素升序,first元素相等时,再按照cond元素升序:
1 #include<iostream>
2 #include<vector>
3 #include<queue>
4using namespace std;
5int main(){
6    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > coll;
7    pair<int,int> a(3,4);报班
8    pair<int,int> b(3,5);
9    pair<int,int> c(4,3);
10    coll.push(c);
11    coll.push(b);
12    coll.push(a);
13while(!pty())
14    {
15        cout<&p().first<<"\t"<&p().cond<<endl;
16        coll.pop();
17    }
18return0;
19 }
2.3 对于⾃定义类型,则必须重载operator<;或者重写仿函数。
2.3.1 重载operator<;的例⼦:返回true时,说明左边形参的优先级低于右边形参
1 #include <iostream>
2 #include <queue>
3using namespace std;
4struct Node{
5int x, y;
6    Node(int a=0, int b=0):
7        x(a),y(b){}
8 };
9bool operator<(Node a, Node b){//返回true时,说明a的优先级低于b
10//x值较⼤的Node优先级低(x⼩的Node排在队前)
英语四级考试作文万能句及万能模板11//x相等时,y⼤的优先级低(y⼩的Node排在队前)
12if( a.x== b.x ) return a.y> b.y;
13return a.x> b.x;
14 }
15int main(){
16    priority_queue<Node> q;
17for( int i= 0; i< 10; ++i )sort
18    q.push( Node( rand(), rand() ) );
19while( !q.empty() ){
20        cout << q.top().x << '' << q.top().y << endl;
21        q.pop();
22    }
23return0;
estimated24 }
⾃定义类型重载operator<;后,声明对象时就可以只带⼀个模板参数。
但此时不能像基本类型这样声明priority_queue<Node,vector<Node>,greater<Node> >,原因是greater<Node>没有定义,如果想⽤这种⽅法定义则可以重载operator >。
bindwood例⼦:返回的是⼩顶堆。但不怎么⽤,习惯是重载operator<。
1 #include <iostream>
2 #include <queue>
3using namespace std;
4struct Node{
piano怎么读5int x, y;
6    Node( int a= 0, int b= 0 ):
7        x(a), y(b) {}
8 };
9bool operator>( Node a, Node b ){//返回true,a的优先级⼤于b
10//x⼤的排在队前部;x相同时,y⼤的排在队前部
11if( a.x== b.x ) return a.y> b.y;
12return a.x> b.x;
13 }
14int main(){
15    priority_queue<Node,vector<Node>,greater<Node> > q;
设计方案英文16for( int i= 0; i< 10; ++i )
17    q.push( Node( rand(), rand() ) );
18while( !q.empty() ){
19        cout << q.top().x << '' << q.top().y << endl;
20        q.pop();
21    }
22return0;
23 }
2.3.2 重写仿函数的例⼦(返回值排序与2.3.1相同,都是⼩顶堆。先按x升序,x相等时,再按y升序):
1 #include <iostream>
2 #include <queue>
3using namespace std;
4struct Node{
5int x, y;
6    Node( int a= 0, int b= 0 ):
7        x(a), y(b) {}
8 };
9struct cmp{
10bool operator() ( Node a, Node b ){//默认是less函数
11//返回true时,a的优先级低于b的优先级(a排在b的后⾯)
自我介绍的英文12if( a.x== b.x ) return a.y> b.y;
13return a.x> b.x; }
14 };
15int main(){
16    priority_queue<Node, vector<Node>, cmp> q;
17for( int i= 0; i< 10; ++i )
18    q.push( Node( rand(), rand() ) );
19while( !q.empty() ){
20        cout << q.top().x << '' << q.top().y << endl;
21        q.pop();
22    }
23return0;
24 }

本文发布于:2023-05-20 13:43:33,感谢您对本站的认可!

本文链接:https://www.wtabcd.cn/fanwen/fan/78/707970.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

标签:类型   元素   返回   参数
相关文章
留言与评论(共有 0 条评论)
   
验证码:
推荐文章
排行榜
Copyright ©2019-2022 Comsenz Inc.Powered by © 专利检索| 网站地图