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

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模拟实现

先查看文档,看看支持了哪些接口:

image-20230806212745863

🐧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

emptysize直接调用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】模拟实现

本章代码&#xff1a;优先级队列模拟实现、priority_queue文档 文章目录 &#x1f408;1. priority_queue介绍&#x1f984;2. priority_queue模拟实现&#x1f427;2.1 构造函数&#x1f427;2.2 建堆向下调整向上调整 &#x1f427;2.3 仿函数&#x1f427;2.4 push & po…...

SpringBoot实现文件记录日志,日志文件自动归档和压缩

&#x1f60a; 作者&#xff1a; Eric &#x1f496; 主页&#xff1a; https://blog.csdn.net/weixin_47316183?typeblog &#x1f389; 主题&#xff1a;SpringBoot实现文件记录日志&#xff0c;日志文件自动归档和压缩 ⏱️ 创作时间&#xff1a; 2023年08月06日 文章目…...

MySQL 窗口函数

聚合函数作为窗口函数 设聚合函数为op语法结构&#xff1a; op(字段名A) over(partition by 字段名B order by 字段名C rows between D1 and D2) 其中&#xff1a; partition by&#xff1a;按照某一字段将数据进行分组 order by&#xff1a;按照某一字段将数据进行排序&…...

0140 数据链路层2

目录 3.数据链路层 3.6局域网 3.7广域网 3.8数据链路层设备 部分习题 3.数据链路层 3.6局域网 3.7广域网 3.8数据链路层设备 部分习题 1.如果使用5类UTP来设计一个覆盖范围为200m的10BASE-T以太网&#xff0c;需要采用的设备是&#xff08;&#xff09; A.放大器 …...

Python字典的应用场景

Python字典是一种无序、可变的数据类型&#xff0c;它由键值对组成。字典在Python中被广泛应用&#xff0c;以下是一些常见的应用场景&#xff1a; 数据存储和检索&#xff1a;字典可以用来存储和检索大量的数据&#xff0c;通过使用键来快速访问对应的值。例如&#xff0c;可以…...

关于外贸跟进客户过程中需要注意的地方

如果你感觉业务进展困难&#xff0c;多去看一些书&#xff0c;多去链接一些人&#xff0c;特别是优秀的人&#xff0c;多交流会让你思维更加开阔&#xff0c;笔记做好实践起来&#xff0c;就会有收获&#xff01; 我记得汪老师说过&#xff1a;跟进客户&#xff0c;当你准备好…...

AI绘画:两组赛博咒语和ComfyUI使用方法

虽迟但到啊&#xff0c;上次说过要发&#xff0c;必然是要发滴&#xff01; 本来我是可以直接发的&#xff0c;但是我又想着发关键词的同时&#xff0c;最好是讲解一下用法&#xff0c;这样更友好。所以就拖了一天&#xff01; 下面先展示一下两套咒语的效果&#xff1a; 这套…...

Nacos源码 (2) 核心模块

返回目录 整体架构 服务管理&#xff1a;实现服务CRUD&#xff0c;域名CRUD&#xff0c;服务健康状态检查&#xff0c;服务权重管理等功能配置管理&#xff1a;实现配置管CRUD&#xff0c;版本管理&#xff0c;灰度管理&#xff0c;监听管理&#xff0c;推送轨迹&#xff0c;聚…...

MySQL之深入InnoDB存储引擎——Buffer Pool

文章目录 一、空闲链表的管理二、缓冲页的哈希处理三、Flush链表的管理四、LRU链表的管理五、脏页刷新六、多Buffer Pool实例 InnoDB存储引擎是基于磁盘存储的&#xff0c;并将其中的记录按照页的方式进行管理。在数据库系统中&#xff0c;由于CPU速度与磁盘速度之间的鸿沟&…...

网络安全(秋招)如何拿到offer?(含面试题)

以下为网络安全各个方向涉及的面试题&#xff0c;星数越多代表问题出现的几率越大&#xff0c;祝各位都能找到满意的工作。 注&#xff1a;本套面试题&#xff0c;已整理成pdf文档&#xff0c;但内容还在持续更新中&#xff0c;因为无论如何都不可能覆盖所有的面试问题&#xf…...

笙默考试管理系统-MyExamTest----classranking(2)

笙默考试管理系统-MyExamTest----classranking&#xff08;2&#xff09; 目录 笙默考试管理系统-MyExamTest----classranking&#xff08;2&#xff09; 一、 笙默考试管理系统-MyExamTest----classranking 二、 笙默考试管理系统-MyExamTest----classranking 三、 笙…...

基于python的一个元素多种定位方式

基于 Python 的 Page Factory 设计模式测试库, 类似于Java的Page Factory模式&#xff0c;旨在减少代码冗余&#xff0c;简单易用&#xff0c;具有高度的可扩展能力。 支持以annotation的方式定义元素 支持同一个元素多种定位方式 支持动态的定位方式 安装 pip install pyth…...

Fastdfs集群搭建

一、简单介绍&#xff1a; FastDFS是一个开源的高性能分布式文件系统&#xff08;DFS&#xff09;。 它的主要功能包括&#xff1a;文件存储&#xff0c;文件同步和文件访问&#xff0c;以及高容量和负载平衡。主要解决了海量数据存储问题&#xff0c;特别适合以中小文件&…...

【深度学习】Vision Transformer论文,ViT的一些见解《 一幅图像抵得上16x16个词:用于大规模图像识别的Transformer模型》

必看文章&#xff1a;https://blog.csdn.net/qq_37541097/article/details/118242600 论文名称&#xff1a; An Image Is Worth 16x16 Words: Transformers For Image Recognition At Scale 论文下载&#xff1a;https://arxiv.org/abs/2010.11929 官方代码&#xff1a;https:…...

在centos7上使用非编译方式安装ffmpeg

很多在centos7上安装ffmpeg的教程都需要使用编译方式的安装&#xff1b;编译时间较长而且需要配置; 后来搜索到可以通过加载rpm 源的方式实现快速便捷操作 第一种方式&#xff1a; 首先需要安装yum源&#xff1a; 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启动!)

&#x1f468;‍&#x1f393;作者简介&#xff1a;一位即将上大四&#xff0c;正专攻机器学习的保研er &#x1f30c;上期文章&#xff1a;机器学习&&深度学习——卷积神经网络&#xff08;LeNet&#xff09; &#x1f4da;订阅专栏&#xff1a;机器学习&&深度…...

小白到运维工程师自学之路 第六十四集 (dockerfile构建tomcat、mysql、lnmp、redis镜像)

一、tomcat&#xff08;更换jdk&#xff09; 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驱动器&#xff0c;可支持最大224点&#xff08;56SEGx4COM&#xff09;或者最大416点&#xff08;52SEGx8COM&#xff09;的LCD屏。单片机可通过I2C接口配置显示参数和读写显示数据&#xff0c;也可通过指令进入省电模式。其高抗干扰&#xff…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...