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

【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++】优先级队列(底层代码解释)

一. 定义 优先级队列是一个容器适配器&#xff0c;他可以根据不同的需求采用不同的容器来实现这个数据结构&#xff0c;优先级队列采用了堆的数据结构&#xff0c;默认使用vector作为容器&#xff0c;且采用大堆的结构进行存储数据。 &#xff08;1&#xff09;在第一个构造函数…...

华为模拟器防火墙配置实验(二)

一.实验拓扑 二.实验要求 1&#xff0c;DMZ区内的服务器&#xff0c;办公区仅能在办公时间内&#xff08;9&#xff1a;00 - 18&#xff1a;00&#xff09;可以访问&#xff0c;生产区的设备全天可以访问. 2&#xff0c;生产区不允许访问互联网&#xff0c;办公区和游客区允许…...

group 与查询字段

需求 每周周一&#xff0c;统计菜单在过去一周&#xff0c;点击次数&#xff0c;和点击人数&#xff08;同一个人访问多次按一次计算&#xff09; 表及数据 日志表 CREATE TABLE t_data_log ( id varchar(50) NOT NULL COMMENT 主键id, operation_object varchar(500) DE…...

PlantUML 教程:绘制时序图

绘制时序图是 PlantUML 的一个强大功能&#xff0c;下面是详细的 PlantUML 时序图教程&#xff0c;帮助你理解如何使用它来创建清晰的时序图。 基本概念 时序图&#xff08;Sequence Diagram&#xff09;用于展示对象之间的交互以及它们之间的消息传递顺序。它主要由以下元素…...

自定义ViewGroup-流式布局FlowLayout(重点:测量和布局)

效果 child按行显示&#xff0c;显示不下就换行。 分析 继承ViewGrouponDraw()不重写&#xff0c;使用ViewGroup的测量-重点 &#xff08;测量child、测量自己&#xff09;布局-重点 &#xff08;布局child&#xff09; 知识点 执行顺序 构造函数 -> onMeasure() -> …...

C++的入门基础(二)

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

显示产业如何突破芯片短板

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

STM32HAL库+ESP8266+cJSON+微信小程序_连接华为云物联网平台

STM32HAL库ESP8266cJSON微信小程序_连接华为云物联网平台 实验使用资源&#xff1a;正点原子F407 USART1&#xff1a;PA9P、A10&#xff08;串口打印调试&#xff09; USART3&#xff1a;PB10、PB11&#xff08;WiFi模块&#xff09; DHT11&#xff1a;PG9&#xff08;采集数据…...

debian或Ubuntu中开启ssh允许root远程ssh登录的方法

debian或Ubuntu中开启ssh允许root远程ssh登录的方法 前因&#xff1a; 因开发需要&#xff0c;需要设置开发板的ssh远程连接。 操作步骤如下&#xff1a; 安装openssh-server sudo apt install openssh-server设置root用户密码&#xff1a; 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中如何处理死锁&#xff1f; 2. MySQL中的主从复制是如何实现的&#xff1f; 3. MySQL中的慢查询日志是什么&#xff1f;如何使用它来优化性能&#xff1f; 4.存储过程 一、定义与基本概念 二、特点与优势 三、类型与分类 四、创建与执行 五、示例 六、总…...

tensorflow之欠拟合与过拟合,正则化缓解

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

vue实现a-model弹窗拖拽移动

通过自定义拖拽指令实现 实现效果 拖动顶部&#xff0c;可对整个弹窗实施拖拽&#xff08;如果需要拖动底部、中间内容实现拖拽&#xff0c;把下面的ant-modal-header对应改掉就行&#xff09; 代码实现 编写自定义指令 新建一个ts / js文件&#xff0c;用ts举例 import V…...

速盾:如何加强网站的安全性

随着互联网的快速发展&#xff0c;网站的安全性变得越来越重要。CDN&#xff08;内容分发网络&#xff09;是一种常见的网络加速服务&#xff0c;它可以将网站的静态内容分发到全球各地的服务器上&#xff0c;以提供更快的访问速度。然而&#xff0c;CDN 也存在一些安全风险&am…...

【PyTorch单点知识】自动求导机制的原理与实践

文章目录 0. 前言1. 自动求导的基本原理2. PyTorch中的自动求导2.1 创建计算图2.2 反向传播2.3 反向传播详解2.4 梯度清零2.5 定制自动求导 3. 代码实例&#xff1a;线性回归的自动求导4. 结论 0. 前言 按照国际惯例&#xff0c;首先声明&#xff1a;本文只是我自己学习的理解&…...

【Java】搜索引擎设计:信息搜索怎么避免大海捞针?

一、内容分析 我们准备开发一个针对全网内容的搜索引擎&#xff0c;产品名称为“Bingoo”。 Bingoo的主要技术挑战包括&#xff1a; 针对爬虫获取的海量数据&#xff0c;如何高效地进行数据管理&#xff1b;当用户输入搜索词的时候&#xff0c;如何快速查找包含搜索词的网页…...

【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…...

痉挛性斜颈对生活有哪些影响?

痉挛性斜颈&#xff0c;这个名字听起来可能并不熟悉&#xff0c;但它实际上是一种神经系统疾病&#xff0c;影响着全球数百万人的生活质量。它以一种无法控制的方式&#xff0c;使患者的颈部肌肉发生不自主的收缩&#xff0c;导致头部姿势异常。对于患者来说&#xff0c;痉挛性…...

Javassist 修改 jar 包里的 class 文件

前言 Javassist 是一个用于处理 Java 字节码的类库&#xff0c;可以用以修改 class 文件或 jar 包里的 class 文件。 简单来说我们用Java编写的代码是放在 java 格式的代码文件里&#xff0c;在编译的时候会编译为 class 格式的字节码文件&#xff0c;然后一般所有 class 文件…...

交换机的二三层原理

相同VLAN的交换机交换原理&#xff08;二层交换原理&#xff09;&#xff1a; 交换机收到数据帧&#xff0c;首先会检查数据帧的VLAN标签和目标MAC&#xff0c;若属于相同VLAN&#xff0c;且该目标MAC在本地MAC表中&#xff0c;则直接根据出接口进行数据转发 不同VLAN的交换机…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

命令行关闭Windows防火墙

命令行关闭Windows防火墙 引言一、防火墙:被低估的"智能安检员"二、优先尝试!90%问题无需关闭防火墙方案1:程序白名单(解决软件误拦截)方案2:开放特定端口(解决网游/开发端口不通)三、命令行极速关闭方案方法一:PowerShell(推荐Win10/11)​方法二:CMD命令…...

归并排序:分治思想的高效排序

目录 基本原理 流程图解 实现方法 递归实现 非递归实现 演示过程 时间复杂度 基本原理 归并排序(Merge Sort)是一种基于分治思想的排序算法&#xff0c;由约翰冯诺伊曼在1945年提出。其核心思想包括&#xff1a; 分割(Divide)&#xff1a;将待排序数组递归地分成两个子…...

window 显示驱动开发-如何查询视频处理功能(三)

​D3DDDICAPS_GETPROCAMPRANGE请求类型 UMD 返回指向 DXVADDI_VALUERANGE 结构的指针&#xff0c;该结构包含特定视频流上特定 ProcAmp 控件属性允许的值范围。 Direct3D 运行时在D3DDDIARG_GETCAPS的 pInfo 成员指向的变量中为特定视频流的 ProcAmp 控件属性指定DXVADDI_QUER…...

虚拟机网络不通的问题(这里以win10的问题为主,模式NAT)

当我们网关配置好了&#xff0c;DNS也配置好了&#xff0c;最后在虚拟机里还是无法访问百度的网址。 第一种情况&#xff1a; 我们先考虑一下&#xff0c;网关的IP是否和虚拟机编辑器里的IP一样不&#xff0c;如果不一样需要更改一下&#xff0c;因为我们访问百度需要从物理机…...