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

【C++初阶】模拟实现优先级队列priority_queue

在这里插入图片描述

👦个人主页:@Weraphael
✍🏻作者简介:目前学习C++和算法
✈️专栏:C++航路
🐋 希望大家多多支持,咱一起进步!😁
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注✨


目录

  • 一、priority_queue的介绍
  • 二、为什么priority_queue不像stack和queue一样使用deque作为其底层存储数据的容器呢
  • 三、priority_queue的常见操作
  • 四、模拟实现priority_queue
      • 4.1 构造函数
      • 4.2 删除堆顶元素pop
      • 4.3 插入push
      • 4.4 获取堆顶元素top
      • 4.5 判断是否为空empty
      • 4.6 获取个数大小size
  • 五、仿函数
      • 5.1 什么是仿函数
      • 5.2 实现priority_queue的仿函数

一、priority_queue的介绍

在这里插入图片描述

  • priority_queue是一个容器适配器,默认使用vector作为其底层存储数据的容器
  • priority_queuevector上使用了堆heap的算法将vector中元素构造堆的结构,因此,priority_queue就是堆默认情况下是大堆。(如何构造成小堆在【仿函数】会讲解到)

二、为什么priority_queue不像stack和queue一样使用deque作为其底层存储数据的容器呢

  1. 这是因为vector在插入和删除元素时具有较好的性能表现。

在堆中插入新元素时,为了保持堆的特性(大堆/小堆)。则需要通过不断地比较和移动元素来完成。vector作为一个连续的内存块,可以更高效地进行元素的插入操作。

相比之下,deque在插入和删除操作时,需要考虑在数组的两端进行操作(头部和尾部),并且要进行元素的移动操作,使得时间复杂度稍高于vector

尽管deque在头部和尾部插入/删除操作上有一些优势,但对于优先级队列这种需要频繁访问和处理最高优先级元素的场景来说,vector更加合适

  1. 弹出pop元素:若要得到堆顶的元素,需要将堆顶元素与最后一个元素交换,并重新调整堆使其满足堆的性质。同样,由于vector是连续存储的,这个操作也可以更高效地进行。

  2. deque的存储空间不是连续的,因此在使用时需要更多的空间,可能会导致空间的浪费。

三、priority_queue的常见操作

在这里插入图片描述

#include <iostream>
#include <queue>
using namespace std;// priority_queue的常见操作int main()
{// 默认是大堆priority_queue<int> pq;pq.push(3);pq.push(5);pq.push(1);pq.push(4);pq.push(0);while (!pq.empty()){cout << pq.top() << ' ';pq.pop();}cout << endl;return 0;
}

【输出结果】

在这里插入图片描述

注意:优先级队列也是不支持迭代器遍历的!!!

四、模拟实现priority_queue

4.1 构造函数

namespace wj
{template<class T, class container = vector<T>>class priority_queue{	private:void AdjustDown(int parent){// 建大堆// 找左右孩子大的size_t child = parent * 2 + 1;while (child < _con.size()){// 保证右孩子存在if (child + 1 < _con.size() && _con[child + 1] > _con[child]) {++child;}if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}public:// 无参默认构造priority_queue(){}// 带区间的构造template<class InputIterator>priority_queue(InputIterator first, InputIterator last){// 插入数据while (first != last){_con.push_back(*first);++first;}//  建堆操作 (默认是大堆) for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}private:container _con;};
}

插入一个数据,由于还要保持大堆的性质,如果尾插的结点要比其父结点大,就要进行 向上调整

参考博客:点击跳转

4.2 删除堆顶元素pop

void pop()
{// 头尾结点交换,删除swap(_con[0], _con[_con.size() - 1]);_con.pop_back();// 然后再建堆AdjustDown(0);
}

4.3 插入push

void push(const T& val)
{// 尾部插入一个_con.push_back(val);// 再建堆AdjustUp(_con.size() - 1);
}

4.4 获取堆顶元素top

const T& top()
{return _con[0];
}

4.5 判断是否为空empty

bool empty()
{return _con.empty();
}

4.6 获取个数大小size

size_t size()
{return  _con.size();
}

五、仿函数

5.1 什么是仿函数

  • 仿函数(函数对象)是一种能够被像函数一样调用的对象。它通常是一个类或者结构体,重载了函数调用运算符 operator(),通过重载这个运算符,我们可以将对象当作函数来使用,实现了类似函数的行为。

  • 仿函数可以有自己的状态和成员变量,因此可以在多次调用中保持状态。它可以接受参数,并返回一个值。

例如,定义一个加法仿函数可以这样实现:

struct Add 
{int operator()(const int a, const int b) const {return a + b;}
};int main() 
{Add add;int result = add(3, 5);  // 调用仿函数cout << "add(3, 5) = " << result << endl;return 0;
}

在上面的例子中,Add是一个仿函数,它重载了函数调用运算符 operator(),使得add对象可以像函数一样被调用。通过add(3, 5),我们可以得到结果8

  • 在C++ 中,仿函数是一种灵活且强大的编程工具,常常用于算法和标准库中的函数对象。

在这里插入图片描述

就比如说sort函数,默认排的是升序

#include <iostream>
#include <algorithm>
using namespace std;int main()
{int arr[] = { 5,1,4,2,0,3 };int arrSize = sizeof(arr) / sizeof(arr[0]);// less<int> 默认可以不写sort(arr, arr + arrSize, less<int>());for (int i = 0; i < arrSize; i++){cout << arr[i] << ' ';}cout << endl;return 0;
}

【输出结果】

在这里插入图片描述

less是库里提供的,其作用就是用于小于不等式比较的函数对象类

在这里插入图片描述

那么如果想排降序,可以将less替换成greater,这也是库里提供的,其作用是用于大于不等式比较的函数对象类

在这里插入图片描述

#include <iostream>
#include <algorithm>
using namespace std;int main()
{int arr[] = { 5,1,4,2,0,3 };int arrSize = sizeof(arr) / sizeof(arr[0]);// less<int> 默认可以不写sort(arr, arr + arrSize, greater<int>());for (int i = 0; i < arrSize; i++){cout << arr[i] << ' ';}cout << endl;return 0;
}

【输出结果】

在这里插入图片描述

5.2 实现priority_queue的仿函数

namespace wj
{template<class T, class container = vector<T>, class Compare = less<T>>class priority_queue{private:void AdjustDown(int parent){Compare com;// 建大堆// 找左右孩子大的size_t child = parent * 2 + 1;while (child < _con.size()){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;}}}void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}public:// 无参默认构造priority_queue(){}// 带区间的构造template<class InputIterator>priority_queue(InputIterator first, InputIterator last){// 插入数据while (first != last){_con.push_back(*first);++first;}//  建堆操作 (默认是大堆) for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}void pop(){// 头尾结点交换,删除swap(_con[0], _con[_con.size() - 1]);_con.pop_back();// 然后再建堆AdjustDown(0);}void push(const T& val){// 尾部插入一个_con.push_back(val);// 再建堆AdjustUp(_con.size() - 1);}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return  _con.size();}private:container _con;};
}

注意:如果在priority_queue中放自定义类型的数据,用户需要在自定义类型中提供>或者<的重载。

namespace wj
{template<class T, class container = vector<T>, class Compare = less<T>>class priority_queue{private:void AdjustDown(int parent){Compare com;// 建大堆// 找左右孩子大的size_t child = parent * 2 + 1;while (child < _con.size()){// 改动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;}}}void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}public:// 无参默认构造priority_queue(){}// 带区间的构造template<class InputIterator>priority_queue(InputIterator first, InputIterator last){// 插入数据while (first != last){_con.push_back(*first);++first;}//  建堆操作 (默认是大堆) for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}void pop(){// 头尾结点交换,删除swap(_con[0], _con[_con.size() - 1]);_con.pop_back();// 然后再建堆AdjustDown(0);}void push(const T& val){// 尾部插入一个_con.push_back(val);// 再建堆AdjustUp(_con.size() - 1);}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return  _con.size();}private:container _con;};// 日期类class Date{public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d);private:int _year;int _month;int _day;};ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}
}

相关文章:

【C++初阶】模拟实现优先级队列priority_queue

&#x1f466;个人主页&#xff1a;Weraphael ✍&#x1f3fb;作者简介&#xff1a;目前学习C和算法 ✈️专栏&#xff1a;C航路 &#x1f40b; 希望大家多多支持&#xff0c;咱一起进步&#xff01;&#x1f601; 如果文章对你有帮助的话 欢迎 评论&#x1f4ac; 点赞&#x1…...

如何为你的公司选择正确的AIGC解决方案?

如何为你的公司选择正确的AIGC解决方案&#xff1f; 摘要引言词汇解释&#xff08;详细版本&#xff09;详细介绍1. 确定需求2. 考虑技术能力3. 评估可行性4. 比较不同供应商 代码快及其注释注意事项知识总结 博主 默语带您 Go to New World. ✍ 个人主页—— 默语 的博客&…...

Windows下将nginx等可执行文件添加为服务

Windows下将nginx等可执行文件添加为服务 为什么将可执行文件添加为服务&#xff1f;将可执行文件添加为服务的步骤步骤 1&#xff1a;下载和安装 Nginx步骤 2&#xff1a;添加为服务方法一&#xff1a;使用 Windows 自带的 sc 命令方法二&#xff1a;使用 NSSM&#xff08;Non…...

视觉SLAM14讲笔记-第4讲-李群与李代数

李代数的引出&#xff1a; 在优化问题中去解一个旋转矩阵&#xff0c;可能会有一些阻碍&#xff0c;因为它对加法导数不是很友好&#xff08;旋转矩阵加上一个微小偏移量可能就不是一个旋转矩阵&#xff09;&#xff0c;因为旋转矩阵本身还有一些约束条件&#xff0c;那样再求…...

浅析Redis(1)

一.Redis的含义 Redis可以用来作数据库&#xff0c;缓存&#xff0c;流引擎&#xff0c;消息队列。redis只有在分布式系统中才能充分的发挥作用&#xff0c;如果是单机程序&#xff0c;直接通过变量来存储数据是更优的选择。那我们知道进程之间是有隔离性的&#xff0c;那么re…...

【每日一题】2337. 移动片段得到字符串

【每日一题】2337. 移动片段得到字符串 2337. 移动片段得到字符串题目描述解题思路 2337. 移动片段得到字符串 题目描述 给你两个字符串 start 和 target &#xff0c;长度均为 n 。每个字符串 仅 由字符 ‘L’、‘R’ 和 ‘_’ 组成&#xff0c;其中&#xff1a; 字符 ‘L’…...

MySQL 数据库常用命令大全(详细)

文章目录 1. MySQL命令2. MySQL基础命令3. MySQL命令简介4. MySQL常用命令4.1 MySQL准备篇4.1.1 启动和停止MySQL服务4.1.2 修改MySQL账户密码4.1.3 MySQL的登陆和退出4.1.4 查看MySQL版本 4.2 DDL篇&#xff08;数据定义&#xff09;4.2.1 查询数据库4.2.2 创建数据库4.2.3 使…...

中国移动加大布局长三角,打造算力产业新高地

8月27日&#xff0c;以“数实融合算启未来”为主题的2023长三角算力发展大会在苏州举办&#xff0c;大会启动了长三角算力调度枢纽&#xff0c;携手各界推动算力产业高质量发展。 会上&#xff0c;移动云作为第一批算力资源提供方&#xff0c;与苏州市公共算力服务平台签订算力…...

话费、加油卡、视频会员等充值接口如何对接?

现在很多商家企业等发现与用户保持粘性是越来越难了&#xff0c;大多数的用户活跃度都很差&#xff0c;到底该怎么做才能改善这种情况呢&#xff1f; 那么我们需要做的就是投其所好&#xff0c;在与用户保持粘性的app或者积分商城中投入大家感兴趣的物品或者虚拟产品&#xff…...

服务器重启MongoDB无法启动

文章目录 服务器重启MongoDB无法启动背景规划实施 总结 服务器重启MongoDB无法启动 背景 数据库服务器的CPU接近告警值了&#xff0c;需要添加CPU资源&#xff0c;于是乎就在恰当的时间对服务器进行关机&#xff0c;待添加完资源后开机&#xff0c;这样就完成了CPU资源的添加…...

深度刨析数据在内存中的存储

✨博客主页&#xff1a;小钱编程成长记 &#x1f388;博客专栏&#xff1a;进阶C语言 深度刨析数据在内存中的存储 1.数据类型介绍1.1 类型的基本归类 2.整形在内存中的存储2.1 原码、反码、补码2.2 大小端介绍 3.浮点型在内存中的存储3.1 一个例子3.2 浮点数的存储规则3.3指数…...

理解FPGA中的亚稳态

一、前言 大家应该经常能听说到亚稳态这个词&#xff0c;亚稳态主要是指触发器的输出在一段时间内不能达到一个确定的状态&#xff0c;过了这段时间触发器的输出随机选择输出0/1&#xff0c;这是我们在设计时需要避免的。本文主要讲述了FPGA中的亚稳态问题&#xff0c;可以帮助…...

Leetcode86. 分隔链表

给你一个链表的头节点 head 和一个特定值 x &#xff0c;请你对链表进行分隔&#xff0c;使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你应当 保留 两个分区中每个节点的初始相对位置。 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台…...

如何处理 Flink 作业中的数据倾斜问题?

分析&回答 什么是数据倾斜&#xff1f; 由于数据分布不均匀&#xff0c;造成数据大量的集中到一点&#xff0c;造成数据热点。 举例&#xff1a;一个 Flink 作业包含 200 个 Task 节点&#xff0c;其中有 199 个节点可以在很短的时间内完成计算。但是有一个节点执行时间…...

cobbler自动化安装CentOS、windows和ubuntu

环境介绍 同时玩cobbler3.3和cobbler2.8.5 cobbler3.3 系统CentOS8.3 VMware虚拟机 桥接到物理网络 IP: 192.168.1.33 cobbler2.8.5 系统CentOS7.9 VMWare虚拟机 桥接到物理网络 IP&#xff1a;192.168.1.33 安装cobbler3.3 yum源修改 cat /etc/yum.repo.d/Cento…...

springcloud3 GateWay章节-Nacos+gateway动态路由负载均衡4

一 工程结构 1.1 工程 1.2 搭建gatewayapi工程 1.pom文件 <dependency><groupId>junit</groupId><artifactId>junit</artifactId><version>4.13</version><scope>test</scope></dependency><!--gateway--&g…...

RESTful API 面试必问

RESTful API是一种基于 HTTP 协议的 API 设计风格&#xff0c;它提供了一组规范和约束&#xff0c;使得客户端&#xff08;如 Web 应用程序、移动应用等&#xff09;和服务端之间的通信更加清晰、简洁和易于理解。 RESTful API 的设计原则 使用 HTTP 协议&#xff1a;RESTful …...

软件机器人助力行政审批局优化网约车业务流程,推动审批业务数字化转型

随着社会的进步和发展&#xff0c;行政审批业务逐渐趋向于智能化和自动化。近日&#xff0c;某市行政审批局在市场准入窗口引入博为小帮软件机器人大幅度提升了网约车办理业务的效率&#xff0c;创新了原有的业务模式。 软件机器人以其自动化、智能化的特性&#xff0c;优化了网…...

飞天使-python的字符串转义字符元组字典等

文章目录 基础语法数据类型python的字符串运算符输入和输出 数据结构列表与元组字典与集合 参考文档 基础语法 数据类型 数值型 &#xff0c;整数 浮点型 布尔型&#xff0c; 真假&#xff0c; 假范围 字符型 类型转换python的字符串 了解转义字符一些基本的运算 \ 比如一行…...

stm32 uart dma方式接收不定长度字符

一般处理&#xff1a; stm32 uart使用dma接收时&#xff0c;会有自己的数据流中断&#xff0c;数据流中断会调用HAL_UART_RxCpltCallback。但是数据流中断只会在HAL_UART_Receive_DMA函数指定的buffer满时才会触发。 接收不定长度字符&#xff0c;需要和uart的UART_IT_IDLE结…...

Unity性能优化终极利器:MeshFusion Pro

在现代游戏开发中&#xff0c;性能优化始终是一个核心问题。尤其是在大型场景或高复杂度模型的项目中&#xff0c;Draw Call 过多、顶点数量庞大以及实时生成对象都会严重拖慢游戏帧率&#xff0c;影响用户体验。为了应对这些挑战&#xff0c;Unity 开发者社区中出现了大量优化…...

提升代码可读性的可视化注释工具推荐

1. 代码注释的艺术化工具推荐作为一名嵌入式开发者&#xff0c;我深知良好的代码注释对于项目维护和团队协作的重要性。但传统的纯文本注释往往枯燥乏味&#xff0c;缺乏直观性。今天我要分享几款能让你的代码注释"活起来"的神器&#xff0c;它们不仅能提升代码可读性…...

学术研究助手:OpenClaw+Gemma-3-12b-it自动化文献综述生成

学术研究助手&#xff1a;OpenClawGemma-3-12b-it自动化文献综述生成 1. 为什么需要自动化文献综述工具 作为一名经常需要写论文的研究生&#xff0c;我深刻体会到文献综述是整个研究过程中最耗时耗力的环节之一。每次开题或写新论文时&#xff0c;都需要花费数天甚至数周时间…...

ClassGraph构建时扫描:Android注解处理的完整解决方案

ClassGraph构建时扫描&#xff1a;Android注解处理的完整解决方案 【免费下载链接】classgraph An uber-fast parallelized Java classpath scanner and module scanner. 项目地址: https://gitcode.com/gh_mirrors/cl/classgraph ClassGraph是一个超高速并行化的Java类…...

基于机器学习算法的亚马逊用户评论情感分析研究:深入探讨随机森林与决策树模型的应用及其实验评估

《基于随机森林和决策树的亚马逊用户评论情感分析研究》深入探讨了利用机器学习技术对亚马逊用户评论数据进行情感分析的方法&#xff0c;旨在为电商企业提供更精准的用户反馈处理工具&#xff0c;以辅助产品优化和服务改进 通过采用决策树模型和随机森林模型这两种不同的机器学…...

抖音视频批量下载终极指南:5分钟掌握免费去水印技巧

抖音视频批量下载终极指南&#xff1a;5分钟掌握免费去水印技巧 【免费下载链接】douyin-downloader A practical Douyin downloader for both single-item and profile batch downloads, with progress display, retries, SQLite deduplication, and browser fallback support…...

STM32智能展柜控制系统设计与实现

1. 项目概述在博物馆文物保存领域&#xff0c;环境参数的精确控制一直是个技术难点。我最近完成了一个基于STM32的智能展柜控制系统项目&#xff0c;这套方案能够实时监测并调节展柜内的温湿度及光照强度&#xff0c;为珍贵文物提供最佳保存环境。相比传统的人工监测方式&#…...

嵌入式开发关键技术演进与实战经验分享

1. 嵌入式开发的行业现状与核心挑战2023年的嵌入式开发领域呈现出明显的多元化发展趋势。作为一名从业超过十年的嵌入式工程师&#xff0c;我观察到这个行业正在经历从传统单机设备向智能化、网络化方向的快速转型。根据AspenCore最新发布的行业调查报告&#xff0c;目前超过30…...

元宇宙中的软件开发和测试:新场景,新挑战

从二维平面到三维宇宙的范式跃迁我们正站在一个数字时代的分水岭上。元宇宙&#xff0c;这个融合了虚拟现实、增强现实、区块链、人工智能与物联网的复杂数字生态&#xff0c;正将软件测试的战场从熟悉的二维平面界面&#xff0c;推向一个充满无限可能的三维沉浸式宇宙。对于软…...

别急着重装!Stable Diffusion WebUI安装失败后,如何利用现有文件快速恢复(Mac/Windows通用)

别急着重装&#xff01;Stable Diffusion WebUI安装失败后&#xff0c;如何利用现有文件快速恢复&#xff08;Mac/Windows通用&#xff09; 当你兴致勃勃地准备体验Stable Diffusion WebUI的强大功能时&#xff0c;突然在安装过程中遇到错误提示&#xff0c;那种挫败感可想而知…...