当前位置: 首页 > 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结…...

机器人控制系统(RCS)核心算法深度解析:从路径规划到任务调度

在智能制造与智能物流快速发展的背景下&#xff0c;机器人控制系统&#xff08;RCS&#xff09;作为 AGV 集群的“大脑中枢”&#xff0c;其核心算法的设计与优化直接决定了整个系统的运行效率和稳定性。本文系统分析了 RCS 系统中的三大核心算法——​路径规划、冲突解决、任务…...

华为eNSP实战:手把手教你用单臂路由打通不同VLAN,附排错命令清单

华为eNSP单臂路由实战&#xff1a;跨VLAN通信配置与深度排错指南 当企业网络规模扩大时&#xff0c;VLAN隔离是保障安全性和广播域控制的必要手段。但实际业务中&#xff0c;不同部门间的数据交互需求常常需要跨越VLAN边界。在华为认证体系HCIA和HCIP的实验环境中&#xff0c;单…...

Llama-3.2V-11B-cot实战教程:集成Whisper实现音视频+图像联合推理

Llama-3.2V-11B-cot实战教程&#xff1a;集成Whisper实现音视频图像联合推理 1. 项目概述与核心能力 Llama-3.2V-11B-cot是一个强大的视觉语言模型&#xff0c;它不仅能理解图像内容&#xff0c;还能进行系统性推理。这个模型基于LLaVA-CoT论文实现&#xff0c;特别适合需要结…...

大数据领域HBase的备份与恢复方案

大数据领域HBase的备份与恢复方案 关键词&#xff1a;HBase备份恢复、分布式存储、数据持久化、全量备份、增量备份、灾难恢复、快照机制 摘要&#xff1a;本文系统解析HBase分布式环境下的数据备份与恢复技术体系&#xff0c;涵盖核心存储原理、多维度备份策略&#xff08;全量…...

公司SEO推广与关键词策略的关系是什么_公司SEO推广的长期效果如何确保

公司SEO推广与关键词策略的关系是什么_公司SEO推广的长期效果如何确保 什么是SEO推广&#xff1f; 我们来了解一下什么是SEO推广。SEO&#xff0c;全称搜索引擎优化&#xff0c;是通过优化网站内容和结构&#xff0c;提高其在搜索引擎自然排名中的位置&#xff0c;从而吸引更…...

基于BANG语言的Sigmoid算子开发与PyTorch集成实战指南

1. BANG语言与Sigmoid算子开发基础 第一次接触寒武纪BANG语言时&#xff0c;我被它类似CUDA但更简洁的语法设计惊艳到了。这种专为MLU硬件设计的异构编程语言&#xff0c;通过在C/C基础上扩展并行计算特性&#xff0c;让开发者能更高效地利用寒武纪芯片的算力资源。 BANG核心语…...

效率倍增器:OpenClaw+千问3.5-27B自动化邮件处理

效率倍增器&#xff1a;OpenClaw千问3.5-27B自动化邮件处理 1. 为什么需要自动化邮件处理 每天早晨打开邮箱&#xff0c;看到堆积如山的未读邮件时&#xff0c;那种窒息感我至今难忘。作为技术团队的接口人&#xff0c;我的邮箱常年保持着2000未读邮件的状态——重要需求埋没…...

数据转换器(ADC/DAC)核心术语与工程实践解析

1. 数据转换器基础概念解析在电子工程领域&#xff0c;数据转换器&#xff08;ADC/DAC&#xff09;是连接模拟世界与数字系统的关键桥梁。作为一名从业十余年的硬件工程师&#xff0c;我经常遇到新手对这些专业术语感到困惑的情况。本文将系统梳理56个核心术语&#xff0c;结合…...

M24LR64E-R双接口NFC标签驱动与嵌入式集成指南

1. 项目概述NFC Tag M24LR6E 是一款面向嵌入式系统的 Arduino 兼容库&#xff0c;专为驱动 Seeed Studio 推出的 Grove - NFC Tag 模块而设计。该模块核心芯片为 STMicroelectronics 的 M24LR64E-R&#xff0c;是一款高度集成的双接口&#xff08;IC RF&#xff09;近场通信标…...

Arduino驱动OV7670图像传感器:底层时序与跨平台实现

1. Arduino_OV767X 库深度解析&#xff1a;OV7670 CMOS 图像传感器在 Arduino 平台上的底层驱动与工程实践OV7670 是 OmniVision&#xff08;现属韦尔半导体&#xff09;于 2000 年代初推出的超低功耗、单芯片 QVGA&#xff08;320240&#xff09;彩色 CMOS 图像传感器。其采用…...