当前位置: 首页 > 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 搭建的环…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...