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

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

RKNN开发环境搭建2-RKNN Model Zoo 环境搭建

目录 1.简介2.环境搭建2.1 启动 docker 环境2.2 安装依赖工具2.3 下载 RKNN Model Zoo2.4 RKNN模型转化2.5编译C++1.简介 RKNN Model Zoo基于 RKNPU SDK 工具链开发, 提供了目前主流算法的部署例程. 例程包含导出RKNN模型, 使用 Python API, CAPI 推理 RKNN 模型的流程.   本…...