深入理解C++ STL中的优先级队列(priority_queue)详细解析
转自https://blog.****.net/c20182030/article/details/70757660,感谢大佬。
优先队列
引入
优先队列是一种特殊的队列,在学习堆排序的时候就有所了解,点“击”查看。
那么优先队列是什么呢?
说白了,就是一种功能强大的队列。
它的功能强大在哪里呢?
四个字:自动排序。
优先队列的头文件&&声明
首先,你需要
#include<queue> using namespace std;
这两个头文件。
其次,一个优先队列声明的基本格式是:
priority_queue<结构类型> 队列名;
比如:
priority_queue <int> i; priority_queue <duble> d;
不过,我们最为常用的是这几种:
priority_queue <node> q; //node是一个结构体 //结构体里重载了‘<’小于符号 priority_queue <int,vector<int>,greater<int> > q; //不需要#include<vector>头文件 //注意后面两个“>”不要写在一起,“>>”是右移运算符 priority_queue <int,vector<int>,less<int> >q;
我们将在下文来讲讲这几种声明方式的不同。
优先队列的基本操作
以一个名为q的优先队列为例。
q.size();//返回q里元素个数 q.empty();//返回q是否为空,空则返回1,否则返回0 q.push(k);//在q的末尾插入k q.pop();//删掉q的第一个元素 q.top();//返回q的第一个元素 q.back();//返回q的末尾元素
优先队列的特性
上文已经说过了,自动排序。
怎么个排法呢?
在这里介绍一下:
默认的优先队列(非结构体结构)
priority_queue <int> q;
这样的优先队列是怎样的?让我们写程序验证一下。
#include<cstdio> #include<queue> using namespace std; priority_queue <int> q; int main() { q.push(10),q.push(8),q.push(12),q.push(14),q.push(6); while(!q.empty()) printf("%d ",q.top()),q.pop(); }
程序大意就是在这个优先队列里依次插入10、8、12、14、6,再输出。
结果是什么呢? 14 12 10 8 6
也就是说,它是按从大到小排序的!
默认的优先队列(结构体,重载小于)
先看看这个结构体是什么。
struct node { int x,y; bool operator < (const node & a) const { return x<a.x; } };
这个node结构体有两个成员,x和y,它的小于规则是x小者小。
再来看看验证程序:
#include<cstdio> #include<queue> using namespace std; struct node { int x,y; bool operator < (const node & a) const { return x<a.x; } } k; priority_queue <node> q; int main() { k.x=10,k.y=100; q.push(k); k.x=12,k.y=60; q.push(k); k.x=14,k.y=40; q.push(k); k.x=6,k.y=80; q.push(k); k.x=8,k.y=20; q.push(k); while(!q.empty()) { node m=q.top(); q.pop(); printf("(%d,%d) ",m.x,m.y); } }
程序大意就是插入(10,100),(12,60),(14,40),(6,20),(8,20)这五个node。
再来看看它的输出: (14,40) (12,60) (10,100) (8,20) (6,80)
它也是按照重载后的小于规则,从大到小排序的。
less和greater优先队列
还是以int为例,先来声明:
priority_queue <int,vector<int>,less<int> > p; priority_queue <int,vector<int>,greater<int> > q;
话不多说,上程序和结果:
#include<cstdio> #include<queue> using namespace std; priority_queue <int,vector<int>,less<int> > p; priority_queue <int,vector<int>,greater<int> > q; int a[5]= {10,12,14,6,8}; int main() { for(int i=0; i<5; i++) p.push(a[i]),q.push(a[i]); printf("less<int>:") while(!p.empty()) printf("%d ",p.top()),p.pop(); pritntf("\ngreater<int>:") while(!q.empty()) printf("%d ",q.top()),q.pop(); }
结果:
less<int>:14 12 10 8 6
greater<int>:6 8 10 12 14
所以,我们可以知道,less是从大到小,greater是从小到大。
作个总结
为了方便,在平时,建议大家写:
priority_queue<int,vector<int>,less<int> >q; priority_queue<int,vector<int>,greater<int> >q;
平时如果用从大到小不用后面的vector<int>,less<int>
,可能到时候要改成从小到大,你反而会搞忘怎么写greater<int>
,反而得不偿失。
总结
优先队列到此就作了个小结。
其实不管是队列,还是优先队列,都不仅仅只有我讲的这些,还有更多可以探索。
学,无止境。
推荐阅读
-
【2022新手指南】Java编程进阶之路 - 六、技术架构篇 ### MySQL索引底层解析与优化实战 - 你会讲解MySQL索引的数据结构吗?性能调优技巧知多少? - Redis深度揭秘:你知道多少?从基础到哨兵、主从复制全梳理 - Redis持久化及哨兵模式详解,还有集群搭建和Leader选举黑箱打开 - Zookeeper是个啥?特性和应用场景大公开 - ZooKeeper集群搭建攻略及 Leader选举、读写一致性、共享锁实现细节 - 探究ZooKeeper中的Leader选举机制及其在分布式环境中的作用 - Zab协议深入剖析:原理、功能与在Zookeeper中的核心地位 - RabbitMQ全方位解读:工作模式、消费限流、可靠投递与配置策略 - 设计者视角:RabbitMQ过期时间、死信队列与延时队列实践指南 - RocketMQ特性和应用场景揭示:理解其精髓与差异化优势 - Kafka详细介绍:特性及广泛应用于实时数据处理的场景解析 - ElasticSearch实力揭秘:特性概述与作为搜索引擎的广泛应用 - MongoDB认知升级:非关系型数据库的优势阐述,安装与使用实战教学 - BIO/NIO/AIO网络模型对比:掌握它们的区别与在网络编程中的实际应用 - Netty带你飞:理解其超快速度背后的秘密,包括线程模型分析 - 网络通信黑科技:Netty编解码原理与常用编解码器的应用,Protostuff实战演示 - 解密Netty粘包与拆包现象,怎样有效应对这一常见问题 - 自定义Netty心跳检测机制,轻松调整检测间隔时间的艺术 - Dubbo轻骑兵介绍:核心特性概览,服务降级实战与其实现益处 - Dubbo三大神器解读:本地存根与本地伪装的实战运用与优势呈现 ----------------------- 七、结语与回顾
-
C++编程:实战教程 - 实现栈与队列(Deque) 容器适配器,探讨Stack和Queue的实现及Queueue(Deque)的问题。深入理解:如何模拟实现Priority Queue (优先级队列) - 实例与练习。续集:仿函数在C++中的二次探索
-
深入理解C++ STL中的优先级队列(priority_queue)详细解析
-
快速掌握C++ STL中的priority_queue(优先级队列)基础教程
-
深入理解C++ STL: priority_queue(优先级队列)的工作原理及仿函数的应用与实战讲解
-
深入理解并实战演示 C++ 优先级队列 priority_queue 的工作原理与实现