当前位置: 首页 > news >正文

【STL专题】优先级队列priority_queue的使用和模拟实现,巧妙利用仿函数解决优先级

  欢迎来到 CILMY23的博客

🏆本篇主题为:优先级队列priority_queue的使用和模拟实现,巧妙利用仿函数解决优先级

🏆个人主页:CILMY23-CSDN博客

🏆系列专栏: C++ | C语言 | 数据结构与算法 | Linux | 算法专题 

🏆感谢观看,支持的可以给个一键三连,点赞收藏+评论。如果你觉得有帮助,还可以点点关注


目录

前言

 优先级队列的使用

优先级队列的常用接口

 实例演示

优先级队列的模拟实现

如何控制优先级?


前言

上期我们讲了栈和队列的使用和模拟实现,本期我们将探究priority_queue,优先级队列的使用和模拟实现,并应用仿函数来解决优先级的问题。


 优先级队列的使用

我们还是从官方文档看起, 

  1. 优先级队列是容器适配器的一种,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
  2. 此语法类似于堆,在堆中可以随时插入元素,并且只能检索堆的最大元素(优先级队列中位于顶部的元素)。
  3. 优先级队列被设计成容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。
  4. 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:        
    • empty():检测容器是否为空
    • size():返回容器中有效元素个数
    • front():返回容器中第一个元素的引用
    • push_back():在容器尾部插入元素
  5. 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。
  6. 需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

不难看出实际上的优先级队列和使用堆没什么差别,当然从接口上我们也不难看出,其次是它没有单独的头文件,它和queue公用一个头文件,都是queue.h。

优先级队列的常用接口

接口功能
bool empty() const;检测优先级队列是否为空,是返回true,否则返回
false
const value_type& top() const;返回优先级队列中最大(最小元素),即堆顶元素
void push (const value_type& val);在优先级队列中插入元素x
void pop();删除优先级队列中最大(最小)元素,即堆顶元素

 实例演示

优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。注意:默认情况下priority_queue是大堆。

215. 数组中的第K个最大元素

我们可以通过这个例子来看。

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int> pq;for (auto& e : nums) {pq.push(e);}// 删除前K-1个元素for (int i = 0; i < k - 1; i++) {pq.pop();}return pq.top();}
};

本题要求在一个整数数组中找到第k个最大的元素,且必须设计时间复杂度为O(n)的算法。如果我们使用堆排序,就可以发现时间复杂度为O(nlogn),建堆的时间代价是O(n),删除的总代价是O(klogn),因为k<n,故渐进时间复杂为O(n+klogn)=O(nlogn)。

那如果我们想实现小堆就可以使用greater,functional,它是greater算法的头文件,创建实例,priority_queue<int, vector<int>, greater<int>>

优先级队列的模拟实现

首先我们先写好各类接口函数,以及容器适配器。

template<class T,class Container = vector<T>>
class priority_queue
{
public:bool empty() const{}size_t size() const{}const T& top() const{}void push(const T& x){}void pop(){}private:Container _con;
};

大部分和堆的实现都类似,可以参照过去的文章,堆的模拟。那这里的判空,大小,堆顶接口函数都很容易写,重点还是插入和删除,这里的插入还是和以前一样,先插入到末尾,然后再向上调整。

void push(const T& val)
{_con.push_back(val);Adjustup(_con.size() - 1);
}Adjustup(int child)
{int parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

 在C++中我们不再像过去那样造轮子确实会轻松不少,利用交换函数swap和插入函数就能节省很多时间。

删除,我们说堆的删除是删除堆顶数据,所以我们进行首尾交换然后再进行向下调整。

void pop()
{if (_con.empty()){return ;}swap(_con.front(), _con.back());_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[child] < _con[parent]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

注意,这里在找左孩子和右孩子的时候必须要考虑到二者都在size之内,否则就会越界报错啦。

如何控制优先级?

过去我们控制优先级是在qsort中用函数指针解决的,而在c++中我们用仿函数解决。

什么是仿函数?

仿函数(Functor)是 C++ 中通过重载 operator() 运算符的类或结构体,其对象可以像函数一样被调用。它常用于定制算法的行为,例如排序规则、比较逻辑等,相比普通函数指针,仿函数能携带状态(成员变量),灵活性更高。 

 例如我们在算法algorithm中使用sort,我们可以利用两个仿函数,来控制排序的逻辑。

struct greater
{bool operator()(int a, int b){return a > b;}
};sort(vec.begin(), vec.end(), greater());

 priority_queue 的仿函数

 

在我们的priority_queue中,它默认为大堆,而这里使用的是less,less表示父节点值 >= 子节点(最大堆),实际就是子节点要小于父节点,我们原先的逻辑是如果子节点大于父节点,我们就交换,所以这里我们可以把逻辑变通一下,如果父节点小于子节点,我们就交换两个值,于是我们这里的仿函数就和库里一样了。

template<class T>struct less
{bool operator()(const T& x,const T& y){return x < y;}
};//向上调整
void AdjustUp(int child)
{int parent = (child - 1) / 2;while (child > 0){Compare com;//子节点大于父节点//if (_con[child] > _con[parent])//父节点小于子节点//if(_con[parent] > _con[child])if(com(_con[parent],_con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

同理,把向下调整也改造一下,删除完后,greater就是子节点大于父节点,也就是父节点小于等于子节点,我们原先的逻辑是如果父节点比子节点大,我们就交换父子节点。

template<class T>struct greater
{bool operator()(const T& x, const T& y){return x > y;}
};void AdjustDown(int parent)
{int child = parent * 2 + 1;while (child < _con.size()){Compare com;//如果左孩子比右孩子大,则从右孩子开始//if (child +1 < _con.size() && _con[child] > _con[child +1])//if (child +1 < _con.size() && _con[child + 1] < _con[child])if (child + 1 < _con.size() && com(_con[child] , _con[child + 1])){ ++child;}if (com(_con[parent] ,_con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}

到这里我们的优先级队列就实现完了,主要还是利用仿函数进行一个控制,我们可以利用仿函数控制大堆和小堆。

相关文章:

【STL专题】优先级队列priority_queue的使用和模拟实现,巧妙利用仿函数解决优先级

欢迎来到 CILMY23的博客 &#x1f3c6;本篇主题为&#xff1a;优先级队列priority_queue的使用和模拟实现&#xff0c;巧妙利用仿函数解决优先级 &#x1f3c6;个人主页&#xff1a;CILMY23-CSDN博客 &#x1f3c6;系列专栏&#xff1a; C | C语言 | 数据结构与算法 | Linux…...

CPU、SOC、MPU、MCU--详细分析四者的区别

一、CPU 与SOC的区别 1.CPU 对于电脑&#xff0c;我们经常提到&#xff0c;处理器&#xff0c;内存&#xff0c;显卡&#xff0c;硬盘四大部分可以组成一个基本的电脑。其中的处理器——Central Processing Unit&#xff08;中央处理器&#xff09;。CPU是一台计算机的运算核…...

Node.js 内置模块简介(带示例)

目录 1. fs&#xff08;文件系统&#xff09;模块 2. http 模块 3. path 模块 4. os 模块 5. events 模块 6. crypto 模块 1. fs&#xff08;文件系统&#xff09;模块 fs 模块提供了与文件系统进行交互的功能&#xff0c;包括文件的读写、删除、重命名等操作。它有同步…...

常见的“锁”有哪些?

悲观锁 悲观锁认为在并发环境中&#xff0c;数据随时可能被其他线程修改&#xff0c;因此在访问数据之前会先加锁&#xff0c;以防止其他线程对数据进行修改。常见的悲观锁实现有&#xff1a; 1.互斥锁 原理&#xff1a;互斥锁是一种最基本的锁类型&#xff0c;同一时间只允…...

二级公共基础之数据库设计基础(一) 数据库系统的基本概念

目录 ​​​​​​​前言 一、数据库、数据管理系统和数据库系统 1.数据 2.数据库 3.数据库管理系统 1.数据库管理系统的定义 2.数据库管理系统的功能 1.数据定义功能 2.数据操作功能 3.数据存取控制 4.数据完整性管理 5.数据备份和恢复 6.并发控制 4.数…...

ollama无法通过IP:11434访问

目录 1.介绍 2.直接在ollama的当前命令窗口中修改&#xff08;法1&#xff09; 3.更改ollama配置文件&#xff08;法2&#xff09; 3.1更新配置 3.2重启服务 1.介绍 ollama下载后默认情况下都是直接在本地的11434端口中运行&#xff0c;绑定到127.0.0.1(localhost)&#x…...

简单易懂,解析Go语言中的struct结构体

目录 4. struct 结构体4.1 初始化4.2 内嵌字段4.3 可见性4.4 方法与函数4.4.1 区别4.4.2 闭包 4.5 Tag 字段标签4.5.1定义4.5.2 Tag规范4.5.3 Tag意义 4. struct 结构体 go的结构体类似于其他语言中的class&#xff0c;主要区别就是go的结构体没有继承这一概念&#xff0c;但可…...

java给钉钉邮箱发送邮件

1.开通POP和IMAP 2.引入pom <dependency><groupId>javax.mail</groupId><artifactId>mail</artifactId><version>1.4.7</version> </dependency>3.逻辑 String host "smtp.qiye.aliyun.com"; String port "…...

C++和OpenGL实现3D游戏编程【连载23】——几何着色器和法线可视化

欢迎来到zhooyu的C++和OpenGL游戏专栏,专栏连载的所有精彩内容目录详见下边链接: 🔥C++和OpenGL实现3D游戏编程【总览】 1、本节实现的内容 上一节课,我们在Blend软件中导出经纬球模型时,遇到了经纬球法线导致我们在游戏中模型光照显示问题,我们在Blender软件中可以通过…...

大连本地知识库的搭建--数据收集与预处理_01

1.马蜂窝爬虫 编程语言&#xff1a;Python爬虫框架&#xff1a;Selenium&#xff08;用于浏览器自动化&#xff09;解析库&#xff1a;BeautifulSoup&#xff08;用于解析HTML&#xff09; 2.爬虫策略 目标网站&#xff1a;马蜂窝&#xff08;https://www.mafengwo.cn/&…...

github 推送的常见问题以及解决

文章目录 git add 的时候问题1为什么会发生这种情况&#xff1f;Git 的警告含义如何解决&#xff1f;1. **保持 Git 的默认行为&#xff08;推荐&#xff09;**2. **禁用自动转换**3. **仅在工作目录中禁用转换**4. **统一使用 LF&#xff08;跨平台开发推荐&#xff09;** git…...

stm32单片机个人学习笔记16(SPI通信协议)

前言 本篇文章属于stm32单片机&#xff08;以下简称单片机&#xff09;的学习笔记&#xff0c;来源于B站教学视频。下面是这位up主的视频链接。本文为个人学习笔记&#xff0c;只能做参考&#xff0c;细节方面建议观看视频&#xff0c;肯定受益匪浅。 STM32入门教程-2023版 细…...

Linux | RHEL / CentOS 中 YUM history / downgrade 命令回滚操作

注&#xff1a;英文引文&#xff0c;机翻未校。 在 RHEL/CentOS 系统上使用 YUM history 命令回滚升级操作 作者&#xff1a; 2daygeek 译者&#xff1a; LCTT DarkSun 为服务器打补丁是 Linux 系统管理员的一项重要任务&#xff0c;为的是让系统更加稳定&#xff0c;性能更加…...

BGP状态和机制

BGP邻居优化 为了增加稳定性,通常建议实验回环口来建立邻居。更新源:建立邻居和邻居所学习到的路由的下一跳。多跳:EBGP邻居建立默认选哟直连,因为TTL=1,如果非直连,必须修改TTL。命令备注peer 2.2.2.2 connect-interface lo1配置更新源peer 2.2.2.2 ebgp-max-hop 2配置T…...

温湿度监控设备融入智慧物联网

当医院的温湿度监控设备融入智慧物联网&#xff0c;将会带来许多新的体验&#xff0c;可以帮助医院温湿度监控设备智能化管理&#xff0c;实现设备之间的互联互通&#xff0c;方便医院对温湿度数据进行统一管理和分析。 添加智慧物联网技术&#xff0c;实现对医院温湿度的实时…...

smolagents学习笔记系列(五)Tools-in-depth-guide

这篇文章锁定官网教程中的 Tools-in-depth-guide 章节&#xff0c;主要介绍了如何详细构造自己的Tools&#xff0c;在之前的博文 smolagents学习笔记系列&#xff08;二&#xff09;Agents - Guided tour 中我初步介绍了下如何将一个函数或一个类声明成 smolagents 的工具&…...

前端面试真题 2025最新版

文章目录 写在前文CSS怪异盒模型JS闭包闭包的形成闭包注意点 CSS选择器及优先级优先级 说说flex布局及相关属性Flex 容器相关属性&#xff1a;Flex 项目相关属性 响应式布局如何实现是否用过tailwindcss&#xff0c;有哪些好处好处缺点 说说对象的 prototype属性及原型说说 pro…...

面试八股文--数据库基础知识总结(1)

1、数据库的定义 数据库&#xff08;DataBase&#xff0c;DB&#xff09;简单来说就是数据的集合数据库管理系统&#xff08;Database Management System&#xff0c;DBMS&#xff09;是一种操纵和管理数据库的大型软件&#xff0c;通常用于建立、使用和维护数据库。数据库系统…...

10. docker nginx官方镜像使用方法

本文介绍docker nginx官方镜像使用方法&#xff0c;因为第一次用&#xff0c;在加上对docker也不是很熟&#xff0c;中间踩了一些坑&#xff0c;为了避免下一次用又踩坑&#xff0c;因此记录如下&#xff0c;也希望能够帮到其它小伙伴。 官方镜像页面&#xff1a;https://hub.d…...

[Web 安全] PHP 反序列化漏洞 —— PHP 反序列化漏洞演示案例

关注这个专栏的其他相关笔记&#xff1a;[Web 安全] 反序列化漏洞 - 学习笔记-CSDN博客 PHP 反序列化漏洞产生原因 PHP 反序列化漏洞产生的原因就是因为在反序列化过程中&#xff0c;unserialize() 接收的值可控。 0x01&#xff1a;环境搭建 这里笔者是使用 PhpStudy 搭建的环…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...