开启辅助访问 切换到宽版

奇迹创客社区

 注册
 登录
搜索
热搜: NOIP OIer 神牛
信息学基地社区»论坛 › 青少年信息学 › 信息学奥赛 › priority_queue的用法（含自定义排序方式） ...
返回列表 发新帖
查看: 322|回复: 0

priority_queue的用法（含自定义排序方式）

[复制链接]
oliver

35

主题

54

帖子

4532

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
4532
发表于 2022-3-6 22:20:14 | 显示全部楼层 |阅读模式
priority_queue本质是一个堆。
头文件是#include<queue>
关于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>
  3. using namespace std;
  4. int main(){
  5.     priority_queue<int> q;
  6.     for( int i= 0; i< 10; ++i ) q.push(i);
  7.     while( !q.empty() ){
  8.         cout<<q.top()<<endl;
  9.         q.pop();
  10.     }
  11.     return 0;
  12. }
复制代码
以下代代码返回pair的比较结果，先按照pair的first元素降序，first元素相等时，再按照second元素降序：
  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4. using namespace std;
  5. int 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);
  13.     while(!coll.empty())
  14.     {
  15.         cout<<coll.top().first<<"\t"<<coll.top().second<<endl;
  16.         coll.pop();
  17.     }
  18.     return 0;
  19. }
复制代码
2.2 如果要用到小顶堆，则一般要把模板的3个参数都带进去。STL里面定义了一个仿函数greater<>，基本类型可以用这个仿函数声明小顶堆。
以下代码返回一个升序输出：
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. int main(){
  5.     priority_queue<int, vector<int>, greater<int> > q;
  6.     for( int i= 0; i< 10; ++i ) q.push(10-i);
  7.     while( !q.empty() ){
  8.         cout << q.top() << endl;
  9.         q.pop();
  10.     }
  11.     return 0;
  12. }
复制代码
以下代代码返回pair的比较结果，先按照pair的first元素升序，first元素相等时，再按照second元素升序：
  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4. using namespace std;
  5. int 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);
  13.     while(!coll.empty())
  14.     {
  15.         cout<<coll.top().first<<"\t"<<coll.top().second<<endl;
  16.         coll.pop();
  17.     }
  18.     return 0;
  19. }
复制代码
2.3 对于自定义类型，则必须重载operator<或者重写仿函数。
2.3.1 重载operator<的例子：返回true时，说明左边形参的优先级低于右边形参
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. struct Node{
  5.     int x, y;
  6.     Node(int a=0, int b=0):
  7.         x(a),y(b){}
  8. };
  9. bool operator<(Node a, Node b){//返回true时，说明a的优先级低于b
  10.     //x值较大的Node优先级低（x小的Node排在队前）
  11.     //x相等时，y大的优先级低（y小的Node排在队前）
  12.     if( a.x== b.x ) return a.y> b.y;
  13.     return a.x> b.x;
  14. }
  15. int main(){
  16.     priority_queue<Node> q;
  17.     for( int i= 0; i< 10; ++i )
  18.     q.push( Node( rand(), rand() ) );
  19.     while( !q.empty() ){
  20.         cout << q.top().x << ' ' << q.top().y << endl;
  21.         q.pop();
  22.     }
  23.     return 0;
  24. }
复制代码
自定义类型重载operator<后，声明对象时就可以只带一个模板参数。
但此时不能像基本类型这样声明priority_queue<Node,vector<Node>,greater<Node> >，原因是greater<Node>没有定义，如果想用这种方法定义则可以重载operator >。
例子：返回的是小顶堆。但不怎么用，习惯是重载operator<。
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. struct Node{
  5.     int x, y;
  6.     Node( int a= 0, int b= 0 ):
  7.         x(a), y(b) {}
  8. };
  9. bool operator>( Node a, Node b ){//返回true，a的优先级大于b
  10.     //x大的排在队前部；x相同时，y大的排在队前部
  11.     if( a.x== b.x ) return a.y> b.y;
  12.     return a.x> b.x;
  13. }
  14. int main(){
  15.     priority_queue<Node,vector<Node>,greater<Node> > q;
  16.     for( int i= 0; i< 10; ++i )
  17.     q.push( Node( rand(), rand() ) );
  18.     while( !q.empty() ){
  19.         cout << q.top().x << ' ' << q.top().y << endl;
  20.         q.pop();
  21.     }
  22.     return 0;
  23. }
复制代码
2.3.2 重写仿函数的例子（返回值排序与2.3.1相同，都是小顶堆。先按x升序，x相等时，再按y升序）：
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. struct Node{
  5.     int x, y;
  6.     Node( int a= 0, int b= 0 ):
  7.         x(a), y(b) {}
  8. };
  9. struct cmp{
  10.     bool operator() ( Node a, Node b ){//默认是less函数
  11.         //返回true时，a的优先级低于b的优先级（a排在b的后面）
  12.         if( a.x== b.x ) return a.y> b.y;
  13.         return a.x> b.x; }
  14. };
  15. int main(){
  16.     priority_queue<Node, vector<Node>, cmp> q;
  17.     for( int i= 0; i< 10; ++i )
  18.     q.push( Node( rand(), rand() ) );
  19.     while( !q.empty() ){
  20.         cout << q.top().x << ' ' << q.top().y << endl;
  21.         q.pop();
  22.     }
  23.     return 0;
  24. }
复制代码


回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

津ICP备19006949号-1 | 津公网安备12010102000465号

快速回复 返回顶部 返回列表