【C++】优先级队列(底层代码解释)
一. 定义
优先级队列是一个容器适配器,他可以根据不同的需求采用不同的容器来实现这个数据结构,优先级队列采用了堆的数据结构,默认使用vector作为容器,且采用大堆的结构进行存储数据。
(1)在第一个构造函数中的第三个参数中,less是大堆,greater是小堆
(2)第二个构造函数的含义是支持使用容器的迭代器区间进行构造
二. 代码实现与解释
2.1 堆中的向上调整和向下调整
(1)向上调整(插入)
在进行插入时,我们首先将插入的节点放在最后一个位置上,然后进行向上调整。
大堆的向上调整: 如果子节点比父节点大则子节点和父节点交换位置
小堆的向上调整: 如果子节点比父节点小则子节点和父节点交换位置
(2)向下调整(删除)
在进行删除数据时我们会把第需要删除的一个元素和最后一个元素交换位置,接着删除尾部的元素,然后把第一个元素向下调整到合适的位置。
大堆的向下调整:找到父节点后,再找到左右节点中较大的那个节点,如果父节点小于子节点中较大的那个节点的话,则交换位置
小堆的向下调整:找到父节点后,再找到左右节点中较小的那个节点,如果父节点大于子节点中较大的那个节点的话,则交换位置
以下是大堆的实现:
template<class T,class container = vector<T>>
class priority_queue
{
public:void adjust_up(int child){Compare com;size_t parent = (child - 1) / 2;while (child > 0){if (_con[parent]< _con[child]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}}void adjust_down(int parent){int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size()&& _con[child ] > _con[child+1]){++child;}if ( _con[parent]< _con[child]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}}void pop(){swap(_con[0], _con[size() - 1]);_con.pop_back();adjust_down(0);}const& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}void push(const T& x){_con.push_back(x);adjust_up(_con.size()-1);}
private:container _con;
};
2.2 仿函数
定义:仿函数就是定义一个类,在这个类中我们进行对符号()进行运算符重载,再用这个类构造一个对象,这个对象可以像函数一样去使用,以下是仿函数的定义与使用。
意义:代替函数指针
Tip:有一点我们需要注意 ,在C++库的排序函数中,我们想要让函数帮助我们升序或者降序排序时我们也需要传递一个参数给 sort(),但是在这里我们给sort传递的是一个less或者greater类型的对象,而不是像在这里的一个类型。
2.3 任意定义大堆小堆
2.1 中介绍了如何建立一个大堆的结构,那么对于不同的场景,我们也可能使用小堆,那么如果库函数中像2.1这么写的话我们就无法使用小堆了,那么为了解决以上的问题我们提出了以下的解决方案。
在函数模板中写一个仿函数的模板
template<class T,class container = vector<T>,class Compare = Less<T>>
这里的 class container 接收的是一个容器的类型(这里默认使用的是vector),而 class compare接收的是接受的是一个仿函数的类名(默认采用Less)。仿函数Less的作用是返回前者是否小于后者的结果,Greater 的作用是返回前者是否大于后者的结果。
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<int,vector<int>,Less<int>> pq;
建立小堆:
priority_queue<int,vector<int>,Greater<int>> pq;
以下是模拟实现优先级队列的代码
#pragma once
#include<vector>
namespace hjy
{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;}};template<class T,class container = vector<T>,class Compare = Less<T>>class priority_queue{public:void adjust_up(int child){Compare com;size_t parent = (child - 1) / 2;while (child > 0){if(com(_con[parent],_con[child]))//if (_con[parent]< _con[child]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}}void adjust_down(int parent){int child = parent * 2 + 1;while (child < _con.size()){/*if (child + 1 < _con.size()&& _con[child ] > _con[child+1])*/if (child + 1 < _con.size()&&com(_con[child],_con[child+1])){++child;}if(com(_con[parent]<_con[child]))//if ( _con[parent]< _con[child]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}}void pop(){swap(_con[0], _con[size() - 1]);_con.pop_back();adjust_down(0);}const& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}void push(const T& x){_con.push_back(x);adjust_up(_con.size()-1);}private:container _con;};
}
相关文章:

【C++】优先级队列(底层代码解释)
一. 定义 优先级队列是一个容器适配器,他可以根据不同的需求采用不同的容器来实现这个数据结构,优先级队列采用了堆的数据结构,默认使用vector作为容器,且采用大堆的结构进行存储数据。 (1)在第一个构造函数…...

华为模拟器防火墙配置实验(二)
一.实验拓扑 二.实验要求 1,DMZ区内的服务器,办公区仅能在办公时间内(9:00 - 18:00)可以访问,生产区的设备全天可以访问. 2,生产区不允许访问互联网,办公区和游客区允许…...

group 与查询字段
需求 每周周一,统计菜单在过去一周,点击次数,和点击人数(同一个人访问多次按一次计算) 表及数据 日志表 CREATE TABLE t_data_log ( id varchar(50) NOT NULL COMMENT 主键id, operation_object varchar(500) DE…...
PlantUML 教程:绘制时序图
绘制时序图是 PlantUML 的一个强大功能,下面是详细的 PlantUML 时序图教程,帮助你理解如何使用它来创建清晰的时序图。 基本概念 时序图(Sequence Diagram)用于展示对象之间的交互以及它们之间的消息传递顺序。它主要由以下元素…...

自定义ViewGroup-流式布局FlowLayout(重点:测量和布局)
效果 child按行显示,显示不下就换行。 分析 继承ViewGrouponDraw()不重写,使用ViewGroup的测量-重点 (测量child、测量自己)布局-重点 (布局child) 知识点 执行顺序 构造函数 -> onMeasure() -> …...

C++的入门基础(二)
目录 引用的概念和定义引用的特性引用的使用const引用指针和引用的关系引用的实际作用inlinenullptr 引用的概念和定义 在语法上引用是给一个变量取别名,和这个变量共用同一块空间,并不会给引用开一块空间。 取别名就是一块空间有多个名字 类型& …...

显示产业如何突破芯片短板
尽管中国在显示IC领域面临一定的不足,但新技术的不断涌现为中国企业提供了重要的发展机遇。随着手机、平板电脑和液晶电视对显示屏性能要求的不断提高,显示驱动IC也必须相应地发展,向更高分辨率、更大尺寸和更低功耗的方向迈进。例如…...

STM32HAL库+ESP8266+cJSON+微信小程序_连接华为云物联网平台
STM32HAL库ESP8266cJSON微信小程序_连接华为云物联网平台 实验使用资源:正点原子F407 USART1:PA9P、A10(串口打印调试) USART3:PB10、PB11(WiFi模块) DHT11:PG9(采集数据…...
debian或Ubuntu中开启ssh允许root远程ssh登录的方法
debian或Ubuntu中开启ssh允许root远程ssh登录的方法 前因: 因开发需要,需要设置开发板的ssh远程连接。 操作步骤如下: 安装openssh-server sudo apt install openssh-server设置root用户密码: sudo passwd root允许root用户…...
C++《日期》实现
C《日期》实现 头文件实现文件 头文件 在该文件中是为了声明函数和定义类成员 using namespace std; class Date {friend ostream& operator<<(ostream& out, const Date& d);//友元friend istream& operator>>(istream& cin, Date& d);//…...
【面试题】MySQL(第三篇)
目录 1. MySQL中如何处理死锁? 2. MySQL中的主从复制是如何实现的? 3. MySQL中的慢查询日志是什么?如何使用它来优化性能? 4.存储过程 一、定义与基本概念 二、特点与优势 三、类型与分类 四、创建与执行 五、示例 六、总…...

tensorflow之欠拟合与过拟合,正则化缓解
过拟合泛化性弱 欠拟合解决方法: 增加输入特征项 增加网络参数 减少正则化参数 过拟合的解决方法: 数据清洗 增大训练集 采用正则化 增大正则化参数 正则化缓解过拟合 正则化在损失函数中引入模型复杂度指标,利用给w增加权重,…...

vue实现a-model弹窗拖拽移动
通过自定义拖拽指令实现 实现效果 拖动顶部,可对整个弹窗实施拖拽(如果需要拖动底部、中间内容实现拖拽,把下面的ant-modal-header对应改掉就行) 代码实现 编写自定义指令 新建一个ts / js文件,用ts举例 import V…...
速盾:如何加强网站的安全性
随着互联网的快速发展,网站的安全性变得越来越重要。CDN(内容分发网络)是一种常见的网络加速服务,它可以将网站的静态内容分发到全球各地的服务器上,以提供更快的访问速度。然而,CDN 也存在一些安全风险&am…...
【PyTorch单点知识】自动求导机制的原理与实践
文章目录 0. 前言1. 自动求导的基本原理2. PyTorch中的自动求导2.1 创建计算图2.2 反向传播2.3 反向传播详解2.4 梯度清零2.5 定制自动求导 3. 代码实例:线性回归的自动求导4. 结论 0. 前言 按照国际惯例,首先声明:本文只是我自己学习的理解&…...

【Java】搜索引擎设计:信息搜索怎么避免大海捞针?
一、内容分析 我们准备开发一个针对全网内容的搜索引擎,产品名称为“Bingoo”。 Bingoo的主要技术挑战包括: 针对爬虫获取的海量数据,如何高效地进行数据管理;当用户输入搜索词的时候,如何快速查找包含搜索词的网页…...
【Python】ModuleNotFoundError: No module named ‘distutils.util‘ bug fix
【Python】ModuleNotFoundError: No module named distutils.util bug fix 1. error like this2. how to fix why this error occured , because i remove the origin version python of ubuntu of 20.04. then the system trapped in tty1 , you must make sure the laptop li…...
痉挛性斜颈对生活有哪些影响?
痉挛性斜颈,这个名字听起来可能并不熟悉,但它实际上是一种神经系统疾病,影响着全球数百万人的生活质量。它以一种无法控制的方式,使患者的颈部肌肉发生不自主的收缩,导致头部姿势异常。对于患者来说,痉挛性…...
Javassist 修改 jar 包里的 class 文件
前言 Javassist 是一个用于处理 Java 字节码的类库,可以用以修改 class 文件或 jar 包里的 class 文件。 简单来说我们用Java编写的代码是放在 java 格式的代码文件里,在编译的时候会编译为 class 格式的字节码文件,然后一般所有 class 文件…...
交换机的二三层原理
相同VLAN的交换机交换原理(二层交换原理): 交换机收到数据帧,首先会检查数据帧的VLAN标签和目标MAC,若属于相同VLAN,且该目标MAC在本地MAC表中,则直接根据出接口进行数据转发 不同VLAN的交换机…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...

华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

热烈祝贺埃文科技正式加入可信数据空间发展联盟
2025年4月29日,在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上,可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞,强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...