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接口配置显示参数和读写显示数据,也可通过指令进入省电模式。其高抗干扰ÿ…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...

Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...

九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
手动给中文分词和 直接用神经网络RNN做有什么区别
手动分词和基于神经网络(如 RNN)的自动分词在原理、实现方式和效果上有显著差异,以下是核心对比: 1. 实现原理对比 对比维度手动分词(规则 / 词典驱动)神经网络 RNN 分词(数据驱动)…...
【系统架构设计师-2025上半年真题】综合知识-参考答案及部分详解(回忆版)
更多内容请见: 备考系统架构设计师-专栏介绍和目录 文章目录 【第1题】【第2题】【第3题】【第4题】【第5题】【第6题】【第7题】【第8题】【第9题】【第10题】【第11题】【第12题】【第13题】【第14题】【第15题】【第16题】【第17题】【第18题】【第19题】【第20~21题】【第…...
Async-profiler 内存采样机制解析:从原理到实现
引言 在 Java 性能调优的工具箱中,async-profiler 是一款备受青睐的低开销采样分析器。它不仅能分析 CPU 热点,还能精确追踪内存分配情况。本文将深入探讨 async-profiler 实现内存采样的多种机制,结合代码示例解析其工作原理。 为什么需要内…...
MySQL用户远程访问权限设置
mysql相关指令 一. MySQL给用户添加远程访问权限1. 创建或者修改用户权限方法一:创建用户并授予远程访问权限方法二:修改现有用户的访问限制方法三:授予特定数据库的特定权限 2. 修改 MySQL 配置文件3. 安全最佳实践4. 测试远程连接5. 撤销权…...