priority_queue的用法「建议收藏」

priority_queue的用法「建议收藏」priority_queue本质是一个堆。1.头文件是#include<queue>2.关于priority_queue中元素的比较模板申明带3个参数:priority_queu

大家好,又见面了,我是你们的朋友全栈君。

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>
 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 } 

 

 

参考:http://www.cnblogs.com/flyoung2008/articles/2136485.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/154473.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • goland的激活码_通用破解码

    goland的激活码_通用破解码,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • centos安装git服务器_自己搭建github服务器

    centos安装git服务器_自己搭建github服务器环境说明CentOS7.x最小安装安装Git$yuminstallgit创建一个git用户组和用户,用来运行git服务$groupaddgit$addusergit-ggit禁止git用户登录:修改/etc/passwd文件git:x:1000:1000::/home/git:/bin/bash后面改为:git:x:1000:1000::/home/git:/bin/git…

  • html5添加网页背景音乐完整代码_网页添加音乐播放

    html5添加网页背景音乐完整代码_网页添加音乐播放方式一:<audiosrc=”static/sound/happyBirthday.mp3″autoplay=”autoplay”preload=”auto”controls=”controls”></audio>或<audioautoplay=……><sourcesrc=”static/sound/happyBirthda…

  • 数据库去重有几种方法_去重数据库

    数据库去重有几种方法_去重数据库概述转发这个主要是有时会有重复数据的需求,留一个查询方法,大家有空也可以测试一下..一、Oracle数据库去重(推荐放在在第6点)1、环境准备可以看到“ALLEN”和“SMITH”这两个人的数据重复了,现在要求表中name重复的数据只保留一行,其他的删除。CREATETABLEhwb(idint,namevarchar(10));INSERTINTOhwbVALUES(1,’TOM’);INSERTINTOhwbVALUES(2,’A

  • Opencv学习笔记(九)光流法

    Opencv学习笔记(九)光流法原创文章,转贴请注明:http://blog.csdn.net/crzy_sparrow/article/details/7407604   本文目录:     一.基于特征点的目标跟踪的一般方法     二.光流法     三.opencv中的光流法函数    四.用类封装基于光流法的目标跟踪方法     五.完整代码     六.参考文献

  • macOS安装yarn

    macOS安装yarnmacOS安装yarn最近在使用Jeecg框架,也需要yarn支持。1.通过HomeBrew安装brewinstallyarn2.升级yarnbrewupgradeyarn3.查看版本号yarn-v

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号