【C++】priority_queue模拟实现过程中值得注意的点

👀樊梓慕:个人主页

 🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

🌝每一个不曾起舞的日子,都是对生命的辜负


前言

本篇文章旨在记录博主在模拟实现priority_queue适配器中遇到的一些问题,希望与大家共勉。


欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。

=========================================================================

GITEE相关代码:🌟fanfei_c的仓库🌟

=========================================================================


1.priority_queue的介绍

  • priority_queue顾名思义:『 优先级队列』;
  • 人话:

priority_queue就是基于vector容器的堆,所以未来涉及到『 堆的应用』都可以使用priority_queue适配器。

默认为大堆。

同样通过模板参数的方式来决定底层容器和构建小堆。

比如:

  • 使用『 vector』作为底层容器,内部构造『 大堆』结构。
priority_queue<int, vector<int>, less<int>> q1;
  • 使用『 vector』作为底层容器,内部构造『 小堆』结构。
priority_queue<int, vector<int>, greater<int>> q2;
  • 不指定底层容器和内部需要构造的堆结构,采用默认即vector、大堆。
priority_queue<int> q;

比较奇怪的是:

构建大堆要传less,构建小堆要传greater,容易记混。

  • 『 大堆』less就是逐渐变小;
  • 『 小堆』greater就是逐渐变大。

2.堆的回顾

2.1向上调整算法

向上调整算法的前提是『 祖先是堆』。

以小堆为例:

1.给定向上调整的起点(孩子节点下标),根据起点下标计算双亲节点下标。

孩子节点与双亲结点间的下标关系:

  • child=parent*2+1 || child=parent*2+2;
  • parent=(child-1)/2;

2.比较孩子节点与双亲节点数值大小,若孩子节点小于于双亲节点,则交换两者,并将孩子节点的下标更新为之前的双亲节点下标,根据最新的孩子节点下标重新计算双亲节点下标,重复这一过程直到孩子节点为根节点。

//堆的向上调整(小堆)
void AdjustUp(vector<int>& v, int child)
{int parent = (child - 1) / 2; //通过child计算parent的下标while (child > 0)//调整到根结点的位置截止{if (v[child] < v[parent])//孩子结点的值小于父结点的值{//将父结点与孩子结点交换swap(v[child], v[parent]);//继续向上进行调整child = parent;parent = (child - 1) / 2;}else{break;}}
}

2.2向下调整算法

向下调整算法的前提是『 左右子树是堆』。

以小堆为例:

1.给定向下调整的起点(双亲节点下标)和节点总数,根据起点下标计算孩子节点下标。

注意:向下调整时,若有两个孩子节点,则需要确保调整的是较小的孩子节点。

2.比较孩子节点与双亲节点数值大小,若孩子节点小于双亲节点,则交换两者,并将双亲节点的下标更新为之前的孩子节点下标,根据最新的双亲节点下标重新计算孩子节点下标,重复这一过程直到孩子节点超出节点总数。

//堆的向下调整(小堆)
void AdjustDown(vector<int>& v, int n, int parent)
{//child记录左右孩子中值较大的孩子的下标int child = 2 * parent + 1;//先默认其左孩子的值较小while (child < n){if (child + 1 < n && v[child+1] < v[child])//右孩子存在并且右孩子比左孩子还小{child = child + 1;//较小的孩子改为右孩子}if (v[child] < v[parent])//左右孩子中较小孩子的值比父结点还小{//将父结点与较小的子结点交换swap(v[child], v[parent]);//继续向下进行调整parent = child;child = 2 * parent + 1;}else{break;}}
}

3.构建大小堆的模板参数问题『仿函数 』 

这里同样涉及到模板参数的传递问题。

在学习堆时,我们知道可以通过改变比较方式从而实现建大堆或者建小堆:

但我们不能每次都手动的去改变这个符号从而满足用户需求。

所以这里我们同样可以利用『 仿函数』来解决这一问题。

仿函数是一个类或结构体,它重载了operator()运算符,使其可以像函数一样被调用。

仿函数的实例可以像函数指针一样传递给STL算法或容器的操作,从而实现自定义行为。

如同我们今天的例子,_com是less类的实例对象,less类重载了操作符(),使其类似于函数调用,内部实现比较大小的功能返回布尔值,_com()就是仿函数,该仿函数模拟了函数行为,使if的判断条件为真或假,从而达到我们>、<的目的。 

 

  • 函数参数传参是在『 使用时传参』,传递的是『 对象』;
  • 模板参数传参是在『 编译时传参』,传递的是『 类型』。

4.模拟实现源码

#pragma oncenamespace F
{//比较方式:减小堆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 = std::vector<T>, class Compare = less<T>>class priority_queue{public://向上调整void adjust_up(int child){int parent = (child - 1) / 2;while (child > 0){//通过模板参数Compare确定是否需要交换结点位置if (_com(_con[child],_con[parent])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}//向下调整void adjust_down(int parent){int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _com(_con[child+1],_con[child])){++child;}if (_com(_con[child], _con[parent])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;//底层容器Compare _com;//比较方式};
}

=========================================================================

如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容

🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏+关注 ~🌟

=========================================================================

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/243186.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

HCIA vlan练习

目录 实验拓扑 实验要求 实验步骤 1、交换机创建vlan 2、交换机上的各个接口划分到对应vlan中 3、trunk干道 4、路由器单臂路由 5、路由器DHCP设置 实验测试 华为交换机更换端口连接模式报错处理 实验拓扑 实验要求 根据图划分vlan&#xff0c;并通过DHCP给主机下发…

Docker(三)使用 Docker 镜像:从仓库获取镜像;管理本地主机上的镜像;介绍镜像实现的基本原理

作者主页&#xff1a; 正函数的个人主页 文章收录专栏&#xff1a; Docker 欢迎大家点赞 &#x1f44d; 收藏 ⭐ 加关注哦&#xff01; 使用 Docker 镜像 在之前的介绍中&#xff0c;我们知道镜像是 Docker 的三大组件之一。 Docker 运行容器前需要本地存在对应的镜像&#x…

c语言冒泡排序

系列文章目录 c语言冒泡排序 c语言冒泡排序 系列文章目录一、冒泡排序原理二、冒泡排序案例 一、冒泡排序原理 有几个数就需要排序几次-1 从数组第一个元素开始和相邻的元素比对&#xff0c;大的元素放在后面&#xff0c;小的放在前面 如&#xff0c;428057139 4与2对比&#x…

「优选算法刷题」:在排序数组中查找元素的第一个和最后个位置

一、题目 给你一个按照非递减顺序排列的整数数组 nums&#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target&#xff0c;返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1&a…

Spring--@Async解析

一、Async 简介 从Spring3开始提供了Async注解&#xff0c;被该注解标注的方法&#xff0c;Spring底层会新建一个线程池或者使用已有的线程池中的线程去异步的执行被标注的方法。 二、Async 工作原理 Async与Transactional 工作原理基本是一样的&#xff0c;也是通过Spring …

【数据结构初阶】——顺序表

本文由睡觉待开机原创&#xff0c;转载请注明出处。 本内容在csdn网站首发 欢迎各位点赞—评论—收藏 如果存在不足之处请评论留言&#xff0c;共同进步&#xff01; 这里写目录标题 1.数据结构2.顺序表线性表顺序表的结构 3.动态顺序表的实现 1.数据结构 数据结构的概念&…

【JavaEE进阶】 Spring Boot⽇志

文章目录 &#x1f38b;关于日志&#x1f6a9;为什么要学习⽇志&#x1f6a9;⽇志的⽤途&#x1f6a9;日志的简单使用 &#x1f384;打印⽇志&#x1f6a9;程序中得到⽇志对象&#x1f6a9;使⽤⽇志对象打印⽇志 &#x1f38d;⽇志格式的说明&#x1f6a9;⽇志级别的作用&#…

QQ数据包解密

Windows版qq数据包格式&#xff1a; android版qq数据包格式&#xff1a; 密钥&#xff1a;16个0 算法&#xff1a;tea_crypt算法 pc版qq 0825数据包解密源码&#xff1a; #include "qq.h" #include "qqcrypt.h" #include <WinSock2.h> #include…

Win10下在Qt项目中配置SQlite3环境

资源下载 官网资源&#xff1a;SQLite Download Page 1、sqlite.h sqlite-amalgamation-3450000.zip (2.60 MiB) 2、sqlite3.def&#xff0c;sqlite3.dll sqlite-dll-win-x64-3450000.zip (1.25 MiB) 3、 win10下安装sqlite3所需要文件 sqlite-tools-win-x64-3450000.zipht…

node介绍

1.node是什么 Node是一个基于Chrome V8引擎的JS运行环境。 Node不是一个独立的语言、node不是JS框架。 Node是一个除了浏览器之外的、可以让JS运行的环境 Node.js是一个让JS运行在服务端的开发平台&#xff0c;是使用事件驱动&#xff0c;异步非阻塞I/O&#xff0c;单线程&…

fastJson和jackson的日期数据处理

目录 1.jackson 2.fastjson 3.总结 1.jackson jackson是spring mvc默认的JSON解析方法&#xff0c;前端的数据序列化处理之后&#xff0c;后端经过反序列化处理可以直接使用实体对象进行接收。后端接口返回实体对象&#xff0c;经过序列化处理后前端可以接收并进行处理。 …

回归预测 | Matlab基于ABC-SVR人工蜂群算法优化支持向量机的数据多输入单输出回归预测

回归预测 | Matlab基于ABC-SVR人工蜂群算法优化支持向量机的数据多输入单输出回归预测 目录 回归预测 | Matlab基于ABC-SVR人工蜂群算法优化支持向量机的数据多输入单输出回归预测预测效果基本描述程序设计参考资料 预测效果 基本描述 1.Matlab基于ABC-SVR人工蜂群算法优化支持…

C++提高编程---模板---类模板

目录 一、类模板 1.模板 2.类模板的作用 3.语法 4.声明 二、类模板和函数模板的区别 三、类模板中成员函数的创建时机 四、类模板对象做函数参数 五、类模板与继承 六、类模板成员函数类外实现 七、类模板分文件编写 八、类模板与友元 九、类模板案例 一、类模板 …

第14章_集合与数据结构拓展练习(前序、中序、后序遍历,线性结构,单向链表构建,单向链表及其反转,字符串压缩)

文章目录 第14章_集合与数据结构拓展练习选择填空题1、前序、中序、后序遍历2、线性结构3、其它 编程题4、单向链表构建5、单向链表及其反转6、字符串压缩 第14章_集合与数据结构拓展练习 选择填空题 1、前序、中序、后序遍历 分析&#xff1a; 完全二叉树&#xff1a; 叶结点…

ElasticSearch的常用增删改查DSL和代码

es增删改查常用语法 我们日常开发中&#xff0c;操作数据库写sql倒是不可能忘记&#xff0c;但是操作es的dsl语句有时候很容易忘记&#xff0c;特地记录一下方便查找。 DSL语句 1、创建索引 -- 创建索引 PUT /my_index {"mappings": {"properties": {&…

Python实现Lasso回归模型

• Tibshirani(1996)提出了Lasso(The Least Absolute Shrinkage and Selectionator operator)算法。 • 通过构造一个一阶惩罚函数获得一个精炼的模型&#xff1b;通过最终确定一些指标&#xff08;变量&#xff09;的系数为零&#xff08;岭回归估计系数等于0的机会微乎其微&a…

【HarmonyOS】体验鸿蒙电商平台的未来之旅!

从今天开始&#xff0c;博主将开设一门新的专栏用来讲解市面上比较热门的技术 “鸿蒙开发”&#xff0c;对于刚接触这项技术的小伙伴在学习鸿蒙开发之前&#xff0c;有必要先了解一下鸿蒙&#xff0c;从你的角度来讲&#xff0c;你认为什么是鸿蒙呢&#xff1f;它出现的意义又是…

【堂堂狼人杀(定制开发)】

堂堂狼人杀游戏♨️风险规避与优势。?零投资也可参与规避五大风险 政策风险(点对点场外交易)账户风险(无资金池&#xff09; 推广风险(免费注册&#xff0c;注册送大礼包&#xff09; 网络风险(大平台&#xff0c;全网场外交易) 人脉风险(预约角色&#xff0c;强制出售) …

力扣hot100 相交链表 超全注释 满级表达

Problem: 160. 相交链表 文章目录 思路复杂度&#x1f496; Ac Code 思路 &#x1f468;‍&#x1f3eb; 参考题解 &#x1f469;‍&#x1f3eb; 参考图解 复杂度 时间复杂度: O ( n m ) O(nm) O(nm) 空间复杂度: 添加空间复杂度, 示例&#xff1a; O ( 1 ) O(1) O(…

python 正则表达式学习(1)

正则表达式是一个特殊的字符序列&#xff0c;它能帮助你方便的检查一个字符串是否与某种模式匹配。 1. 特殊符号 1.1 符号含义 模式描述^匹配字符串的开头$匹配字符串的末尾.匹配任意字符&#xff0c;除了换行符&#xff0c;当re.DOTALL标记被指定时&#xff0c;则可以匹配包…