C++——STL容器【priority_queue】模拟实现

本章代码:优先级队列模拟实现、priority_queue文档
文章目录
- 🐈1. priority_queue介绍
- 🦄2. priority_queue模拟实现
- 🐧2.1 构造函数
- 🐧2.2 建堆
- 向下调整
- 向上调整
- 🐧2.3 仿函数
- 🐧2.4 push & pop操作
- 🐧2.5 top & empty & size
🐈1. priority_queue介绍
priority_queue在STL里面是队列的一种,叫做优先级队列,它的底层是基于堆实现的,默认的是大堆。
它的使用方法与queue类似,可理解为priority_queue是一个可以排序的队列
🦄2. priority_queue模拟实现
先查看文档,看看支持了哪些接口:

🐧2.1 构造函数
priority_queue采用的vector作为容器适配器,那默认构造直接调用vector的就行,然后构造还支持迭代器初始化:
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);}}
}
🐧2.2 建堆
向下调整的时间复杂度是O(N),向上调整的时间复杂度是O(N*logN),所以采用向下调整建堆
详细讲解可查看:数据结构——二叉树(堆、堆排序、二叉树链式结构)
向下调整
//向下调整 默认大堆
void AdjustDown(int parent)
{int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child + 1] > _con[child]){child = child + 1;}if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
向上调整
//向上调整
void AdjustUp(int child)
{int parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
🐧2.3 仿函数
STL的priority_queue默认是大堆,如果想要指定小堆,则需要在参数列表里面指定参数
std::priority_queue<int> maxHeap; // 默认:大堆
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; //小堆
这里我们要实现,就要用到仿函数
仿函数是一个类,它重载了函数调用运算符
operator(),这使得这个类就可以想函数一样被调用
在这里我们就重载operator()来模拟比较函数
template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}};
priority_queue不指定的情况下,默认是大堆,指定模板时将Less设为缺省参数即可
template<class T, class Container = vector<T>, class Compare = Less<T>>
class priority_queue
有了仿函数,我们的向下调整和向上调整在选择建大堆或者小堆的时候,调用这个仿函数即可:
//向下调整 默认大堆
void AdjustDown(int parent)
{Compare com;int child = parent * 2 + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child = child + 1;}//if (_con[child] > _con[parent])if (com(_con[parent], _con[child])){std::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 (_con[child] > _con[parent])if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
🐧2.4 push & pop操作
-
插入操作即在队尾增加一个元素,然后向上调整,保证这还是一个堆
-
删除操作还是模拟堆的操作,将首元素和最后一个元素交换,然后删除队尾元素
这样保证了即使删除之后,下面的还是一个堆,接下来向下调整即可
void pop()
{std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);
}
void push(const T& x)
{_con.push_back(x);AdjustUp(_con.size() - 1);
}
🐧2.5 top & empty & size
这empty和size直接调用vector的接口即可;top查看队头元素,返回队头元素即可
const T& top() const
{return _con[0];
}
bool empty() const
{return _con.empty();
}
size_t size()
{return _con.size();
}
那本期的分享就到这咯,我们下期再见,如果还有下期的话
相关文章:
C++——STL容器【priority_queue】模拟实现
本章代码:优先级队列模拟实现、priority_queue文档 文章目录 🐈1. priority_queue介绍🦄2. priority_queue模拟实现🐧2.1 构造函数🐧2.2 建堆向下调整向上调整 🐧2.3 仿函数🐧2.4 push & po…...
SpringBoot实现文件记录日志,日志文件自动归档和压缩
😊 作者: Eric 💖 主页: https://blog.csdn.net/weixin_47316183?typeblog 🎉 主题:SpringBoot实现文件记录日志,日志文件自动归档和压缩 ⏱️ 创作时间: 2023年08月06日 文章目…...
MySQL 窗口函数
聚合函数作为窗口函数 设聚合函数为op语法结构: op(字段名A) over(partition by 字段名B order by 字段名C rows between D1 and D2) 其中: partition by:按照某一字段将数据进行分组 order by:按照某一字段将数据进行排序&…...
0140 数据链路层2
目录 3.数据链路层 3.6局域网 3.7广域网 3.8数据链路层设备 部分习题 3.数据链路层 3.6局域网 3.7广域网 3.8数据链路层设备 部分习题 1.如果使用5类UTP来设计一个覆盖范围为200m的10BASE-T以太网,需要采用的设备是() A.放大器 …...
Python字典的应用场景
Python字典是一种无序、可变的数据类型,它由键值对组成。字典在Python中被广泛应用,以下是一些常见的应用场景: 数据存储和检索:字典可以用来存储和检索大量的数据,通过使用键来快速访问对应的值。例如,可以…...
关于外贸跟进客户过程中需要注意的地方
如果你感觉业务进展困难,多去看一些书,多去链接一些人,特别是优秀的人,多交流会让你思维更加开阔,笔记做好实践起来,就会有收获! 我记得汪老师说过:跟进客户,当你准备好…...
AI绘画:两组赛博咒语和ComfyUI使用方法
虽迟但到啊,上次说过要发,必然是要发滴! 本来我是可以直接发的,但是我又想着发关键词的同时,最好是讲解一下用法,这样更友好。所以就拖了一天! 下面先展示一下两套咒语的效果: 这套…...
Nacos源码 (2) 核心模块
返回目录 整体架构 服务管理:实现服务CRUD,域名CRUD,服务健康状态检查,服务权重管理等功能配置管理:实现配置管CRUD,版本管理,灰度管理,监听管理,推送轨迹,聚…...
MySQL之深入InnoDB存储引擎——Buffer Pool
文章目录 一、空闲链表的管理二、缓冲页的哈希处理三、Flush链表的管理四、LRU链表的管理五、脏页刷新六、多Buffer Pool实例 InnoDB存储引擎是基于磁盘存储的,并将其中的记录按照页的方式进行管理。在数据库系统中,由于CPU速度与磁盘速度之间的鸿沟&…...
网络安全(秋招)如何拿到offer?(含面试题)
以下为网络安全各个方向涉及的面试题,星数越多代表问题出现的几率越大,祝各位都能找到满意的工作。 注:本套面试题,已整理成pdf文档,但内容还在持续更新中,因为无论如何都不可能覆盖所有的面试问题…...
笙默考试管理系统-MyExamTest----classranking(2)
笙默考试管理系统-MyExamTest----classranking(2) 目录 笙默考试管理系统-MyExamTest----classranking(2) 一、 笙默考试管理系统-MyExamTest----classranking 二、 笙默考试管理系统-MyExamTest----classranking 三、 笙…...
基于python的一个元素多种定位方式
基于 Python 的 Page Factory 设计模式测试库, 类似于Java的Page Factory模式,旨在减少代码冗余,简单易用,具有高度的可扩展能力。 支持以annotation的方式定义元素 支持同一个元素多种定位方式 支持动态的定位方式 安装 pip install pyth…...
Fastdfs集群搭建
一、简单介绍: FastDFS是一个开源的高性能分布式文件系统(DFS)。 它的主要功能包括:文件存储,文件同步和文件访问,以及高容量和负载平衡。主要解决了海量数据存储问题,特别适合以中小文件&…...
【深度学习】Vision Transformer论文,ViT的一些见解《 一幅图像抵得上16x16个词:用于大规模图像识别的Transformer模型》
必看文章:https://blog.csdn.net/qq_37541097/article/details/118242600 论文名称: An Image Is Worth 16x16 Words: Transformers For Image Recognition At Scale 论文下载:https://arxiv.org/abs/2010.11929 官方代码:https:…...
在centos7上使用非编译方式安装ffmpeg
很多在centos7上安装ffmpeg的教程都需要使用编译方式的安装;编译时间较长而且需要配置; 后来搜索到可以通过加载rpm 源的方式实现快速便捷操作 第一种方式: 首先需要安装yum源: yum install epel-release yum install -y https://mirrors.…...
【微信小程序】导出Excel文件
// 导出 doOutExcel() {let fileName 考勤列表wx.request({url: XXX,method: POST,header: {"content-type": "application/json","Authorization": "token " wx.getStorageSync(userInfo).token},data: {}, // 请求参数responseTyp…...
接口测试—知识速查(Postman)
文章目录 接口测试1. 概念2. 原理3. 测试流程4. HTTP协议4.1 URL的介绍4.2 HTTP请求4.2.1 请求行4.2.2 请求头4.2.3 请求体4.2.4 完整的HTTP请求示例 4.3 HTTP响应4.3.1 状态行4.3.2 响应头4.3.3 响应体4.3.4 完整的HTTP请求示例 5. RESTful接口规范6. 测试用例的设计思路6.1 单…...
机器学习深度学习——序列模型(NLP启动!)
👨🎓作者简介:一位即将上大四,正专攻机器学习的保研er 🌌上期文章:机器学习&&深度学习——卷积神经网络(LeNet) 📚订阅专栏:机器学习&&深度…...
小白到运维工程师自学之路 第六十四集 (dockerfile构建tomcat、mysql、lnmp、redis镜像)
一、tomcat(更换jdk) mkdir tomcat cd tomcat/ tar xf jdk-8u191-linux-x64.tar.gz tar xf apache-tomcat-8.5.40.tar.gzvim Dockerfile FROM centos:7 MAINTAINER Crushlinux <syh163.com> ADD jdk1.8.0_191 /usr/local/java ENV JAVA_HOME /us…...
超低功耗水表电器表LCD驱动显示芯片,高抗干扰性能提供LQFP48、LQFP64的封装
VK2C23是一个点阵式存储映射的LCD驱动器,可支持最大224点(56SEGx4COM)或者最大416点(52SEGx8COM)的LCD屏。单片机可通过I2C接口配置显示参数和读写显示数据,也可通过指令进入省电模式。其高抗干扰ÿ…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
