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

C++中的priority_queue模拟实现

目录

priority_queue模拟实现

priority_queue类定义

priority_queue构造函数

priority_queue类push()函数

priority_queue类pop()函数

priority_queue类size()函数

priority_queue类empty()函数

priority_queue类top()函数

仿函数与priority_queue类模拟实现

仿函数


priority_queue模拟实现

实现priority_queue的方式和stack和queue基本类似,因为priority_queue也是一种容器适配器,但是只能使用vector和deque,这里默认使用vector容器作为适配器,因为priority_queue本质是堆结构,所以实现时主要按照堆的实现思路进行

priority_queue类定义

//vector作为默认的容器适配器
template<class T, class Container = vector<T>>
class priority_queue
{
private:Container _con:
}

priority_queue构造函数

priority_queue主要有两种构造函数:

  1. 无参构造函数
  2. 迭代器构造函数

📌

需要注意的是,如果不显式实现两个构造函数,则默认是无参构造,该默认构造将会调用容器适配器的构造函数

//有迭代器构造就必须写显式写空参构造
priority_queue():_con()
{}
//迭代器构造函数
template<class Iterator>
priority_queue(Iterator begin, Iterator end):_con(begin, end)
{//向下调整算法建堆for (int i = (size()-2)/2; i >=0 ; i--){adjustDown(i);}
}

priority_queue类push()函数

因为按照堆实现思路进行,所以push()函数实现思路如下:

  1. 向容器适配器中插入数据
  2. 通过向上/向下调整算法构建堆
//向上调整建堆(以大堆为例)
void 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;}}
}
//向下调整算法
void adjustDown(int parent)
{//获取孩子int child = parent * 2 + 1;while (child < size()){//如果右孩子大于左孩子,更新当前的孩子为右孩子if (child + 1 < 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;}}
}
//push()函数
void push(const T& val)
{//调用指定容器的push_back()函数_con.push_back(val);//找到当前孩子的位置int child = _con.size() - 1;//向上调整建堆//adjustUp(child);//向下调整建堆//获取到最后一个孩子对应的父亲int parent = (child - 1) / 2;for (int i = parent; i >= 0; i--){adjustDown(i);}
}

priority_queue类pop()函数

因为按照堆实现思路进行,所以pop()函数实现思路如下:

  1. 交换根节点数据和最后一个叶子节点的数据
  2. 调用容器适配器的删除,除去最后一个数据
  3. 向下调整重新为堆
//pop()函数
void pop()
{//先交换堆顶数据和最后一个叶子节点数据swap(_con[0], _con[size() - 1]);_con.pop_back();//向下调整算法调整堆adjustDown(0);
}

priority_queue类size()函数

//size()函数
const size_t size()
{return _con.size();
}

priority_queue类empty()函数

//empty()函数
bool empty()
{return _con.empty();
}

priority_queue类top()函数

//top()函数_const版本
const T& top() const
{return _con[0];
}//top()函数_非const版本
T& top()
{return _con[0];
}

仿函数与priority_queue类模拟实现

在前面的模拟实现中,priority_queue默认是小堆的实现,但是如果此时需要实现大堆,就需要改变向上/向下调整算法,但是这种实现方式不能在一个文件里面同时创建出小堆和大堆,所以此时需要一个函数来控制比较大小,此时就可以用到仿函数

仿函数简单介绍

所谓仿函数就是使用类并且重载()运算符,例如对于比较两个数值,小于返回true的仿函数

//仿函数
template<class T>
class less
{
public:bool operator()(const T& val1, const T& val2){return val1 < val2;}
};

同样地,可以实现一个比较两个数值,大于返回true的仿函数

template<class T>
class greater
{
public:bool operator()(const T& val1, const T& val2){return val1 > val2;}
};

所以此时可以使用仿函数修改向上/向下调整算法

//向上调整建堆(以大堆为例)
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;}}
}
//向下调整算法
void adjustDown(int parent)
{//定义仿函数对象,调用对象函数Compare com;//获取孩子int child = parent * 2 + 1;while (child < size()){//如果右孩子大于左孩子,更新当前的孩子为右孩子if (child + 1 < 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;}}
}

此时如果需要实现大堆,则只需要改变Compare的类型即可,下面是小堆和大堆的测试代码

void test()
{//小堆sim_priority_queue::priority_queue<int> pq;//上面的代码等同于//sim_priority_queue::priority_queue<int, vector<int>, sim_priority_queue::less<int>> pq;pq.push(35);pq.push(70);pq.push(56);pq.push(90);pq.push(60);pq.push(25);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;//大堆sim_priority_queue::priority_queue<int, vector<int>, sim_priority_queue::greater<int>> pq2;pq2.push(35);pq2.push(70);pq2.push(56);pq2.push(90);pq2.push(60);pq2.push(25);while (!pq2.empty()){cout << pq2.top() << " ";pq2.pop();}
}int main()
{test();
}
输出结果:
90 70 60 56 35 25
25 35 56 60 70 90

现在考虑前面sort函数中的仿函数

默认情况下,使用sort函数会对一段区间的内容进行升序排列,但是如果需要控制降序排列就需要用到仿函数

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main()
{vector<int> v{30, 2, 45, 4, 46, 78, 11, 25};// 默认升序排列sort(v.begin(), v.end());for (auto num : v){cout << num << " ";}cout << endl;vector<int> v1{30, 2, 45, 4, 46, 78, 11, 25};// 使用仿函数匿名对象改为降序排列sort(v1.begin(), v1.end(), greater<int>());for (auto num : v1){cout << num << " ";}
}
输出结果:
2 4 11 25 30 45 46 78 
78 46 45 30 25 11 4 2 

📌

有了仿函数,除了可以使用内置的一些仿函数,也可自定义自己的仿函数来规定比较方式,这种对于自定义类型并且重载了比较运算符非常便捷

相关文章:

C++中的priority_queue模拟实现

目录 priority_queue模拟实现 priority_queue类定义 priority_queue构造函数 priority_queue类push()函数 priority_queue类pop()函数 priority_queue类size()函数 priority_queue类empty()函数 priority_queue类top()函数 仿函数与priority_queue类模拟实现 仿函数 …...

【Kafka】1.Kafka核心概念、应用场景、常见问题及异常

Kafka 是一个分布式流处理平台&#xff0c;最初由 LinkedIn 开发&#xff0c;后成为 Apache 软件基金会的顶级项目。 它主要用于构建实时数据管道和流式应用程序。它能够高效地处理高吞吐量的数据&#xff0c;并支持消息发布和订阅模型。Kafka 的主要用途包括实时分析、事件源、…...

LTE的EARFCN和band之间的对应关系

一、通过EARFCN查询对应band 工作中经常遇到只知道EARFCN而需要计算band的情况&#xff0c;因此查了相关协议&#xff0c;找到了他们之间的对应关系&#xff0c;可以直接查表&#xff0c;非常方便。 具体见&#xff1a; 3GPP TS 36.101 5.7.3 Carrier frequency and EAR…...

解决问题:Docker证书到期(Error grabbing logs: rpc error: code = Unknown)导致无法查看日志

问题描述 Docker查看日志时portainer报错信息如下&#xff1a; Error grabbing logs: rpc error: code Unknown desc warning: incomplete log stream. some logs could not be retrieved for the following reasons: node klf9fdsjjt5tb0w4hxgr4s231 is not available报错…...

【C语言】预处理器

我们在开始编写一份程序的时候&#xff0c;从键盘录入的第一行代码&#xff1a; #include <stdio.h>这里就使用了预处理&#xff0c;引入头文件。 C预处理器不是编译器的组成部分&#xff0c;但是它是编译过程中一个单独的步骤。简言之&#xff0c;C预处理器只不过是一…...

QtConcurrent::run操作界面ui的注意事项(2)

前面的“QtConcurrent::run操作界面ui的注意事项&#xff08;1&#xff09;”&#xff0c;末尾说了跨线程的问题&#xff0c;引出了Qt千好万好&#xff0c;就是跨线程不好。下面是认为的最简单的解决办法&#xff1a;使用QMetaObject::invokeMethod&#xff08;相比较信号-槽&a…...

黑马程序员HarmonyOS4+NEXT星河版入门到企业级实战教程笔记

HarmonyOS NEXT是纯血鸿蒙&#xff0c;鸿蒙原生应用&#xff0c;彻底摆脱安卓 本课程是基于harmony os4的&#xff0c;与next仅部分api有区别 套件 语言&框架 harmony os design ArkTs 语言 ArkUI 提供各种组件 ArkCompiler 方舟编译器 开发&测试 DevEco Studio 开发…...

嵌入式全栈开发学习笔记---C语言笔试复习大全13(编程题9~16)

目录 9.查找字符数组中字符位置&#xff08;输入hello e 输出2&#xff09;&#xff1b; 10、查找字符数组中字符串的位置&#xff08;输入hello ll 输出3&#xff09;&#xff1b; 11、字符数组中在指定位置插入字符&#xff1b;&#xff08;输入hello 3 a 输出heallo…...

https网站安全证书的作用与免费申请办法

HTTPS网站安全证书&#xff0c;也称为SSL证书&#xff0c;网站通过申请SSL证书将http协议升级到https协议 HTTPS网站安全证书的作用 1 增强用户信任&#xff1a;未使用https协议的网站&#xff0c;用户访问时浏览器会有“不安全”弹窗提示 2 提升SEO排名&#xff1a;搜索引擎…...

自动化测试再升级,大模型与软件测试相结合

近年来&#xff0c;软件行业一直在迅速发展&#xff0c;为了保证软件质量和提高效率&#xff0c;软件测试领域也在不断演进。如今&#xff0c;大模型技术的崛起为软件测试带来了前所未有的智能化浪潮。 软件测试一直是确保软件质量的关键环节&#xff0c;但传统的手动测试方法存…...

centos7 基础命令

一、基础信息&#xff1a; 查看IP地址&#xff1a; ip add 重启网络服务&#xff1a; service network restart 查看网卡配置&#xff1a; cat /etc/sysconfig/network-scripts/ifcfg-ens33 启动网卡: ifup ens33 查看内存: free -m 查看CPU&#xff1a; cat /proc/cpuin…...

【设计模式】之单例模式

系列文章目录 【设计模式】之责任链模式【设计模式】之策略模式【设计模式】之模板方法模式 文章目录 系列文章目录 前言 一、什么是单例模式 二、如何使用单例模式 1.单线程使用 2.多线程使用&#xff08;一&#xff09; 3.多线程使用&#xff08;二&#xff09; 4.多线程使用…...

3d模型实体显示有隐藏黑线?---模大狮模型网

在3D建模和设计领域&#xff0c;细节决定成败。然而&#xff0c;在处理3D模型时&#xff0c;可能会遇到模型实体上出现隐藏黑线的问题。这些黑线可能影响模型的视觉质量和呈现效果。因此&#xff0c;了解并解决这些隐藏黑线的问题至关重要。本文将探讨隐藏黑线出现的原因&#…...

共享购:全新消费模式的探索与实践

在消费模式日益创新的今天&#xff0c;共享购模式以其独特的消费与收益双重机制&#xff0c;吸引了众多消费者的目光。这一模式不仅为消费者带来了全新的购物体验&#xff0c;也为商家和平台带来了可观的收益。 一、会员体系&#xff1a;共享购的基石 在共享购模式下&#xff…...

Java集合 总结篇(全)

Java集合 集合底层框架总结 List 代表的有序&#xff0c;可重复的集合。 ArrayList -- 数组 -- 把他想象成C中的Vector就可以&#xff0c;当数组空间不够的时候&#xff0c;会自动扩容。 -- 线程不安全 LinkedList -- 双向链表 -- 可以将他理解成一个链表&#xff0c;不支持…...

Dubbo分层架构深度解析

引言 Dubbo作为一款备受欢迎的高性能、轻量级的Java RPC框架&#xff0c;在现代分布式系统中扮演着至关重要的角色。随着互联网行业的快速发展&#xff0c;服务间的通信变得越来越频繁&#xff0c;这也使得对于高效、可靠的远程通信方案的需求变得愈发迫切。在这样的背景下&am…...

LocalDate 数据库不兼容问题,因为LocalDate 是 long 类型的

我今天遇到一报错&#xff1a; SqlSession [org.apache.ibatis.session.defaults.DefaultSqlSession316f9272] was not registered for synchronization because synchronization is not active JDBC Connection [HikariProxyConnection2127597288 wrapping com.mysql.cj.jdbc…...

RVM(相关向量机)、CNN_RVM(卷积神经网络结合相关向量机)、RVM-Adaboost(相关向量机结合Adaboost)

当我们谈到RVM&#xff08;Relevance Vector Machine&#xff0c;相关向量机&#xff09;、CNN_RVM&#xff08;卷积神经网络结合相关向量机&#xff09;以及RVM-Adaboost&#xff08;相关向量机结合AdaBoost算法&#xff09;时&#xff0c;每种模型都有其独特的原理和结构。以…...

Java--方法的使用

1.1什么是方法 方法顾名思义就是解决问题的办法&#xff0c;在程序员写代码的时候&#xff0c;会遇到很多逻辑结构一样&#xff0c;解决相同问题时&#xff0c;每次都写一样的代码&#xff0c;这会使代码看起来比较绒余&#xff0c;代码量也比较多&#xff0c;为了解决这个问题…...

linux - 主次设备号自动申请

alloc_chrdev_region 原型如下&#xff0c;该函数向内核申请一个空闲的主设备号。 alloc_chrdev_region(&g_aputriger_dev, 0, APUTRIGER_MAX_NUM, "aputriger0"); 第四个参数是我们使用cat /proc/devices 看到的名称 /*** alloc_chrdev_region() - register a…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

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

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

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...