【C++】STL——priority_queue优先级队列
目录
- 前言
- priority_queue的使用
- 简单使用
- 在OJ中的使用
- priority_queue的模拟实现
- 基本功能
- 仿函数
- 在这里插入图片描述
前言
上一节我们说了stack和queue这两种容器适配器,而priority_queue(优先级队列)同样也是属于容器适配器,它会优先处理级别较高的值,如数字最大的,其实也就是数据结构中的堆。即物理结构上是数组,逻辑结构上是一颗完全二叉树。
priority_queue的使用
简单使用
库里面的priority_queue:cplusplus–priority_queue

优先级队列是一种容器适配器,根据某种严格的弱排序标准,使得它的第一个元素总是它所包含的元素中最大的。
也就类似于堆,其中元素可以随时插入,并且只能检索堆顶元素(优先级队列中位于顶部的元素)。
我们可以先来查看一下priority_queue的类型:
我们使用typeid来查看一个变量的类型。
#include<iostream>
#include<queue>//优先级队列存在于此头文件中
#include<vector>
using namespace std;int main()
{priority_queue<int> pq;cout << typeid(pq).name() << endl;//查看类型return 0;
}

由图,该模板中由两个逗号隔开,代表的意思分别是:
int:所存储的数据类型class std::vector<int,class std::allocator<int> >:底层所使用的容器struct std::less<int>:比较方式,默认是less,即小于比较,决定谁的优先级更高。
priority_queue的接口也不多,就以下几个:
| 函数说明 | 接口说明 |
|---|---|
| empty() | 检测是否为空 |
| size() | 返回元素个数 |
| top() | 返回优先级队列中最大(最小)元素,即堆顶元素 |
| push(x) | 在优先级队列中插入x |
| pop() | 删除优先级队列中最大(最小)元素,即堆顶元素 |
使用也很简单:
#include<iostream>
#include<queue>
#include<vector>
using namespace std;int main()
{priority_queue<int> pq;//cout << typeid(pq).name() << endl;pq.push(5);pq.push(8);pq.push(3);pq.push(1);pq.push(9);while (!pq.empty())//输出默认大堆,底层按小于号排序{cout << pq.top() << " ";pq.pop();}cout << endl;vector<int> v = { 8,3,6,1,9,4,5 };/*priority_queue<int,vector<int>,greater<int>> pq1;for (auto e : v){pq1.push(e);}*///直接使用迭代器构造priority_queue<int, vector<int>, greater<int>> pq1(v.begin(), v.end());while (!pq1.empty())//输出默认大堆,底层按小于号排序{cout << pq1.top() << " ";pq1.pop();}cout << endl;return 0;
}
结果如下:

可以看到,一旦我把默认的less比较方式换成了greater< int >,它就能实现小堆。
由于比较方式是在第三个参数,所以如果需要修改,就要把第二个参数一起写上。这就是为什么中间还要写vector< int >的原因。
在OJ中的使用
Leetcode.数组中第k个大的元素
题目如下:
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

题目的意思还是比较容易理解的。我们优先能想到的就是将数组中的值进行排序然后去重,但是任意一种排序方式的时间复杂度都超过了 O(n) ,此时我们就能想到用堆,它既能去重又能排序,则就可以使用优先级队列来解决。
将所有数放入优先级队列中,默认是大堆,此时不断去除堆顶元素,将前k-1个删掉,再取堆顶元素即可。
代码如下:
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int> pq(nums.begin(), nums.end());for(int i = 1; i < k; i++){pq.pop();}return pq.top();}
};
priority_queue的模拟实现
priority_queue优先级队列,属于容器适配器的一种,它和stack和queue一样,都不需要自己去实现功能,只需要调用底层容器的功能即可,但是为了符合堆的规则,在插入和删除时还是要用到向上调整和向下调整来实现。
我们先来看一下优先级队列的一个框架,为方便理解,我们先将模板中的第三个参数给去除了:
namespace emm//使用命名空间,防止与库里面的发生冲突
{template<class T, class container = vector<int>>//默认底层容器为vectorclass priority_queue{pubilc:private:container _con;};
}
基本功能
对于其判空,取大小以及取堆顶元素都可以直接复用底层容器的实现即可。
bool empty() const
{return _con.empty();
}
size_t size() const
{return _con.size();
}
const T& top() const
{return _con.front();
}
当我想要插入一个元素,我需要先尾插这一个数据,然后根据堆的规则,进行向上调整。
void push(const T& val)
{_con.push_back(val);AdjustUp(size() - 1);
}
void AdjustUp(int child)//大堆
{int parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child])//遵循库里面,小于是大堆//如果孩子节点大于父亲节点,则交换{swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}
可以通过测试来看看:

运行结果可以看出它是一个大堆。
当我想pop即删除堆顶元素时,就要用到``向下调整法,我们不能直接将堆顶元素删除,那样会破坏堆的规则,所以要先将堆顶元素与最后一个元素进行交换然后将其删除,最后利用向下调整为大堆。
代码如下:
void pop()
{swap(_con[0], _con[_con.size() - 1]);//先交换_con.pop_back();//删除最后一个(堆顶)元素AdjustDown(0);//从堆顶开始向下调整
}
void AdjustDown(int parent)
{int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child] < _con[child + 1]){++child;}if (_con[parent] < _con[child])//遵循库里面,小于是大堆{swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}
这样输出就是排好序的数组了:

此时我们将构造函数写上:
//强制生成默认构造
priority_queue() = default;template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)//迭代器区间构造
{while (first != last){push(*first);first++;}
}
仿函数
当我们按照上面正常写法,想把建大堆改成建小堆时,要把向上调整和向下调整中的小于号都改为大于号,这样操作较为繁琐,那么有没有简单一点的操作呢,答案是有的,也就是仿函数。顾名思义,就是对象可以像函数一样调用。
例如:

当然,括号里面带有参数也是可以的。
此时,我们就可以写出两个比较大小的仿函数:
template<class T>
struct less
{bool operator()(const T& x, const T& y){return x < y;}
};
template<class T>
struct greater
{bool operator()(const T& x, const T& y){return x > y;}
};
这样就可以使得比较大小可以像函数一样去使用

此时可以将priority_queue中的模板参数变为3个,而参数3的缺省值就是less:
template<class T, class container = vector<int>,class Compare = less<int>>
此时向上调整和向下调整就变为了:
void AdjustUp(int child)//大堆
{Compare com;//实例化一个对象int parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])//遵循库里面,小于是大堆//如果孩子节点大于父亲节点,则交换if(com(_con[parent],_con[child]))//对象可以像函数一样直接调用{swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}void AdjustDown(int parent)
{Compare com;//实例化一个对象int child = parent * 2 + 1;while (child < _con.size()){/*if (child + 1 < _con.size() && _con[child] < _con[child + 1])*/if (child + 1 < _con.size() && com(_con[child],_con[child+1])){++child;}//if (_con[parent] < _con[child])//遵循库里面,小于是大堆if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}
如果我们想要切换成小堆,就按正常操作,写模版实例化时将参数变为greater< int >即可。
vector<int> v = { 8,3,6,1,9,4,5 };
emm::priority_queue<int> pq2(v.begin(), v.end());
while (!pq2.empty())
{cout << pq2.top() << " ";pq2.pop();
}
cout << endl;emm::priority_queue<int, vector<int>, greater<int>> pq3(v.begin(), v.end());
while (!pq3.empty())//变为小堆,按大于号排序
{cout << pq3.top() << " ";pq3.pop();
}
cout << endl;
感谢大家观看,如果大家喜欢,希望大家一键三连支持一下,如有表述不正确,也欢迎大家批评指正。

相关文章:
【C++】STL——priority_queue优先级队列
目录 前言priority_queue的使用简单使用在OJ中的使用 priority_queue的模拟实现基本功能仿函数在这里插入图片描述 前言 上一节我们说了stack和queue这两种容器适配器,而priority_queue(优先级队列)同样也是属于容器适配器,它会优…...
大数据新视界 --大数据大厂之大数据在智慧城市建设中的应用:打造智能生活的基石
💖💖💖亲爱的朋友们,热烈欢迎你们来到 青云交的博客!能与你们在此邂逅,我满心欢喜,深感无比荣幸。在这个瞬息万变的时代,我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…...
使用枚举来实现策略模式
使用很多if else的场景 public void save(String type,Object data){if("db".equals(type)){saveInDb(data);}else if("file".equals(type)){saveInFile(data);}else if("oss".equals(type)){saveInOss(data);}}使用枚举来解决 public enum Save…...
区块链技术原理
1. 引言 区块链的定义 区块链是一种分布式账本技术(Distributed Ledger Technology,DLT),其核心特征是通过密码学的方式将数据打包成一个个区块,按时间顺序依次相连,形成一个不可篡改、公开透明的链式数据…...
Spring Boot 接口数据加解密
今天聊下接口安全问题,涉及到接口的加密和解密 经常和外部单位接口调用梳理了相关技术方案,主要的需求点如下: 1,尽量少改动,不影响之前的业务逻辑 2,考虑到时间紧迫性,可采用对称性加密方式&…...
2018年计算机网络408真题解析
第一题: 解析:TCP/IP体系结构应用层常用协议及其相应的运输层协议 TCP协议是面向连接可靠数据传输服务,UDP无连接不可靠的数据传输服务,IP无连接不可靠的数据连接服务。 FTP协议,SMTP协议和HTTP协议使用TCP协议提供的面…...
Javascript 脚本查找B站限时免费番剧
目录 前言 脚本编写 脚本 前言 B站的一些番剧时不时会“限时免费”,白嫖党最爱,主打一个又占到便宜的快乐。但是在番剧索引里却没有搜索选项可以直接检索“限时免费”的番剧,只能自己一页一页的翻去查看,非常麻烦。 自己找限…...
YoloV10改进策略:主干网络改进|DeBiFormer,可变形双级路由注意力|全网首发
摘要 在目标检测领域,YoloV10以其高效和准确的性能而闻名。然而,为了进一步提升其检测能力,我们引入了DeBiFormer作为YoloV10的主干网络。这个主干网络的计算量比较大,不过,上篇双级路由注意力的论文受到很大的关注,所以我也将这篇论文中的主干网络用来改进YoloV10,卡多…...
C#学习笔记(一)
C#学习笔记(一) 简介第一章 上位机开发环境之 VS 使用和.NET 平台基础一、安装软件二、创建项目三、第一个Hello world四、解决方案与项目五、Debug 和 Release 的区别六、代码的生产过程七、CLR的其它功能 简介 C# .NET工控上位机开发 在工控领域&…...
MATLAB边缘检测
一、目的: 熟悉边缘检测原理,并运用matlab软件实现图像的canny边缘检测,体会canny边缘检测的优缺点。 二、内容: 编写matlab程序,实现对lena图像的边缘检测,输出程序运行结果。 三、原理或步骤&#x…...
Tortoise SVN 安装汉化教程(乌龟SVN)
1.首先下载 去官网下载 如果下载比较慢的,链接自取 https://pan.quark.cn/s/cb6f2eee3f90 2. 安装Tortoise SVN 无脑next到完成 最后到桌面右键 你就发现svn出来了,但是是英文的!!!! 像我这种英文不好的…...
深入了解Spring重试组件spring-retry
在我们的项目中,为了提高程序的健壮性,很多时候都需要有重试机制进行兜底,最多就场景就比如调用远程的服务,调用中间件服务等,因为网络是不稳定的,所以在进行远程调用的时候偶尔会产生超时的异常࿰…...
海南聚广众达电子商务咨询有限公司靠谱吗怎么样?
在当今这个数字化浪潮席卷全球的时代,抖音电商以其独特的魅力成为了众多商家争相入驻的新蓝海。而在这片浩瀚的电商海洋中,如何找到一家既专业又可靠的合作伙伴,成为了众多商家心中的一大难题。今天,我们就来深入剖析一下海南聚广…...
Java的魔法世界:面向对象编程(OOP)是什么?
这个嘎嘎重要 面向对象编程(OOP)是让Java像玩具世界一样,把现实中的东西变成“对象”,然后让这些对象去互动。你可以想象OOP是Java的“魔法世界”,通过创建“对象”(Object),让它们有…...
软件测试笔记——接口测试
文章目录 一、概念1.接口测试流程2.URL3.HTTP协议4.RESTful5.案例介绍 二、Postman1.Postman软件2.登录接口调试-获取验证码3.登录接口调试-自动关联数据4.合同上传接口-提交请求数据5.提交参数查询6.批量执行7.接口用例设计8.断言8.参数化三、案例1.项目2.课程添加3.课程列表查…...
东方通 TongRDS V2 配置与开机自启指南及 Spring Boot 集成
东方通 TongRDS V2 配置与开机自启指南及 Spring Boot 集成 文章目录 东方通 TongRDS V2 配置与开机自启指南及 Spring Boot 集成一 简述二 配置 cfg.xml1 启用密码访问2 Spring Boot 连接 TongRDS 三 配置 TongRDS 开机自启1 配置 RdsCenter1)设置 RdsCenter.servi…...
在 VS Code 中调试 Tensor 形状不显示的问题及解决方案
文章目录 常见问题解决方案1. 定制类包装和 __repr__ 方法 解释如何应用总结 在使用 VS Code 调试 PyTorch 代码时,可能会遇到一个常见问题:调试时 variables 窗口中不显示 Tensor 的形状信息。这会使得调试时观察数据的结构变得不便,尤其是在…...
Linux 时间获取全面总结
1. 引言 在Linux操作系统中,获取时间是一个基本且重要的功能。本文旨在全面总结Linux系统中获取时间的方法,包括命令行工具和编程接口,帮助读者深入理解Linux时间管理的机制。 2. 命令行工具 2.1 date 命令 date 命令是Linux中最常用的命…...
SQL 自学:游标(Cursors)的理解与应用
在 SQL 中,游标(Cursor)是一种用于处理从数据库中检索出的多行数据的机制。它允许我们逐行地处理查询结果集,而不是一次性处理整个结果集。 一、游标是什么 游标可以看作是一个指向结果集的指针。通过游标,我们可以在…...
IO多路复用概述与epoll简介
一、引言 在网络编程中,高并发的场景下处理大量连接请求是一项挑战。传统的阻塞式IO模型会让线程在等待数据的过程中陷入停顿,导致系统效率低下。为了解决这个问题,IO多路复用应运而生。它允许一个线程同时监听多个文件描述符(如…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...
MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...

