【C++】优先级队列的基本概念以及其模拟实现
文章目录
- 补充知识:仿函数
- 一、优先级队列:
- 1.引入
- 2.介绍
- 二、priority_queue的模拟实现
- 1.大体框架
- 2.私有成员函数:
- 1.向下调整(AdjustDown)
- 2.向上调整(AdjustUp)
- 3.公有成员函数
- 1大小(size).
- 2是否为空(empty).
- 3.移除堆顶的元素(pop)
- 4.元素插入(push)
- 5.堆顶的元素(top)
- 6.构造函数
- 1.默认无参构造
- 2.迭代器构造
补充知识:仿函数
C++仿函数(function object)是一种可以像函数一样调用的对象。仿函数通常是一个类,它重载了函数调用运算符operator(),使得对象可以被调用。

一、优先级队列:
1.引入
优先级队列(Priority Queue)在底层实现上使用了一种称为堆(Heap)的数据结构,通常使用数组(比如C++中的std::vector)来表示。堆是一种完全二叉树数据结构,具有以下特点:
- 堆是一个完全二叉树,也就是说除了最底层,其他层都必须是完全填满的,最底层的节点依次从左到右填充。
2.堆中的每个节点的值都大于等于(或小于等于)其子节点的值,这就是所谓的堆序性质。
2.介绍
- 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
- 此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。
- 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类
- 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭
代器访问,并支持以下操作:
empty():检测容器是否为空
size():返回容器中有效元素个数
front():返回容器中第一个元素的引用
push_back():在容器尾部插入元素
pop_back():删除容器尾部元素- 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。
虽然底层实现中使用了vector,但优先级队列仍然保持了队列的特性,即根据优先级出队元素
二、priority_queue的模拟实现
1.大体框架
namespace simulation {
template<class T, class Container = vector<T>, class Compare = less<T>>//Compare这里传的是仿函数,默认为系统里自带的less仿函数,也可以自己添加//用于比较大小,Container为底层实现容器,默认为vectorclass priority_queue {private://私有成员函数void AdjustDown(int parent) { }void AdjustUp(int child) {}public://公有成员函数void pop() { }void push(const T & x) {}const T& top() { }bool empty() {}size_t size() {}priority_queue(){}private:Container _con;//成员变量};
2.私有成员函数:
1.向下调整(AdjustDown)

图中是在建小堆,但我们代码以大堆为例,除了大于小于的方向不同,但逻辑是一样的
void AdjustDown(int parent) {//向下调整条件:// 左右子树都是大堆/小堆int child = parent * 2 + 1;Compare com;//仿函数的实例化while (child < _con.size()) {if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) {++child;//选出两个孩子中最大的那一个}if (com(_con[parent], _con[child])) {//最大的那一个去与父母比较swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else {break;}}}
2.向上调整(AdjustUp)


void AdjustUp(int child) {//向上调整条件:// 除了child这个位置前面的数据构成堆int parent = (child - 1) / 2;Compare com;while (child > 0) {if (com(_con[parent], _con[child])) {swap(_con[parent], _con[child]);child = parent;//接着向上parent = (child - 1) / 2;}else {break;}}}
3.公有成员函数
1大小(size).
2是否为空(empty).
3.移除堆顶的元素(pop)

void pop() {swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}
4.元素插入(push)

void push(const T& x) {_con.push_back(x);//新元素向上调整AdjustUp(_con.size() - 1);}
5.堆顶的元素(top)
const T& top() {return _con[0];}
6.构造函数
1.默认无参构造
priority_queue() {
//内容可以什么都不写,因为初始化会去内置类型不用管,自定义类型会去调用其
//默认构造函数,这里会直接调用成员变量_con的默认构造
//当你写了迭代器构造后,这个无参构造你必须要有,因为当你写了一个构造函数
//以后,编译器就不会自己再生成默认构造函数}
2.迭代器构造
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);}}
相关文章:
【C++】优先级队列的基本概念以及其模拟实现
文章目录 补充知识:仿函数一、优先级队列:1.引入2.介绍 二、priority_queue的模拟实现1.大体框架2.私有成员函数:1.向下调整(AdjustDown)2.向上调整(AdjustUp) 3.公有成员函数1大小(…...
TextClamp for Vue3.0(Vue3.0的文本展开收起组件)
呦!大家好,好久没有更新博客了,最近实现了一个一直想自己完成的一个东西,就是文本的展开收起组件,以前项目需要用到,自己实现一个又太繁琐,所以那个时候都是用的别人的轮子,现在自己…...
区间预测 | MATLAB实现VAR向量自回归时间序列区间预测
区间预测 | MATLAB实现VAR向量自回归时间序列区间预测 目录 区间预测 | MATLAB实现VAR向量自回归时间序列区间预测预测效果基本介绍程序设计参考资料预测效果 基本介绍 区间预测 | MATLAB实现VAR向量自回归时间序列区间预测 VAR(Vector Autoregression)模型是一种广泛应用于时…...
在 Windows 上搭建 NTP 服务器
文章目录 一、基础环境二、适用场景三、操作步骤四、常用的NTP服务器五、参考资料 版权声明:本文为博主原创文章,于2023年7月30日首发于CSDN,转载请附上原文出处链接和本声明。本文链接:https://blog.csdn.net/u011046671 一、基础…...
应急响应经典案例-FTP 暴力破解
应急响应经典案例-FTP 暴力破解 应急场景日志分析应急处理措施 应急场景 从昨天开始,网站响应速度变得缓慢,网站服务器登录上去非常卡,重启服务器就能保证一段时间的正常访问,网站响应状态时而飞快时而缓慢,多数时间是…...
41. linux通过yum安装postgresql
文章目录 1.下载安装包2.关闭内置PostgreSQL模块:3.安装postgresql服务:4.初始化postgresql数据库:5.设置开机自启动:6.启动postgresql数据库7.查看postgresql进程8.通过netstat命令或者lsof 监听默认端口54329.使用find命令查找了一下postgresql.conf的配置位置10.修改postgre…...
SpringBoot启动流程及自动配置
SpringBoot启动流程源码: 1、启动SpringBoot启动类SpringbootdemoApplication中的main方法。 SpringBootApplication public class SpringbootdemoApplication {public static void main(String[] args) {SpringApplication.run(SpringbootdemoApplication.class, …...
【Linux】进程轻松入门
目录 一, 冯* 诺依曼体系结构 1,存储结构 编辑 二, 操作系统 1,概念 2,设计OS的目的 3,定位 4,如何理解 "管理" 5, 总结 三,进程 1. 概念 那么…...
【使用时空RBF-NN进行非线性系统识别】实现了 RBF、分数 RBF 和时空 RBF 神经网络,用于非线性系统识别研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
Tomcat 安装配置教程及成功后,启动失败报错解决方案
解决方案 我的报错原因是因为我的JDK是1.8的而我的Tomcat是10版本的,可能是因为版本原因吧,我重新装了Tomcat 9就可以启动成功了! 简单说下安装的时候需要注意哪些步骤吧 今天我在安装tomcat10的时候,安装成功后,启…...
C#文件操作从入门到精通(2)——查看某个dll中有哪些函数
kernel32.dll中含有ini文件操作使用的函数,我们可以通过VisualStudio自带的dumpbin.exe查看dll所包含的函数,操作步骤如下: 1、找到dumpbin.exe所在的文件夹 我的电脑中安装了VisualStudio2019社区版以及VisualStudio2017Professional,但是我发现VisualStudio2019社区版中…...
二分查找算法(全网最详细代码演示)
二分查找也称 半查找(Binary Search),它时一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字 有序 排列。 注意:使用二分查找的前提是 该数组是有序的。 在实际开…...
draw up a plan
爱情是美好的,却不是唯一的。爱情只是属于个人化的感情。 推荐一篇关于爱情的美文: 在一个小镇上,有一家以制作精美巧克力而闻名的手工巧克力店,名叫“甜蜜之爱”。这家巧克力店是由一位名叫艾玛的年轻女性经营的,她对…...
抖音seo源码开发源代码开发技术分享
一、 抖音SEO源码开发,需要掌握以下技术: 抖音API接口:抖音提供了丰富的API接口,包括用户信息、视频信息、评论信息等。 数据爬取技术:通过抓包分析抖音接口的数据结构,可以使用Python等编程语言编写爬虫程…...
QEMU(Quick Emulator)
QEMU(Quick Emulator)是一款由法布里斯贝拉等人编写的免费的可执行硬件虚拟化的开源托管虚拟机。它可以通过动态的二进制转换模拟CPU,并提供一组设备模型,使它能够运行多种未修改的客户机OS。QEMU还可以为user-level的进程执行CPU…...
Gateway结合nacos(lb://xxx)无效问题
Gateway结合nacos无效 版本如下: com.alibaba.cloud:spring-cloud-starter-alibaba-nacos-discovery:2021.0.1.0 org.springframework.cloud:spring-cloud-starter-gateway:3.1.1 配置如下: server:port: 7000 spring:application:name: springCloudGa…...
NODEJS笔记
全局对象 global/window console.log/info/warn/error/time/timeEnd process.arch/platform/version/env/kill/pid/nextTick Buffer.alloc(5,abcde) String/toString setTimeout/clearTimeout setInterval/clearInterval setImmediate/clearImmediate process.nextTi…...
无涯教程-jQuery - html( )方法函数
html(val)方法获取第一个匹配元素的html内容(innerHTML)。此属性在XML文档上不可用。 html( ) - 语法 selector.html( ) html( ) - 示例 以下是一个简单的示例,简单说明了此方法的用法- <html><head><title>The jQuery Example</title>…...
Linux vsftp三种模式的简单配置部署
环境:Debian 6.1.27-1kali1 (2023-05-12) vsftpd 安装 --查看是否当前系统是否已安装 apt list --installed | grep vsftpd 没有安装的话,就正常安装 apt-get update apt-get install vsftpd 一、匿名用户模式 分享一些不重要文件,任…...
6.1.tensorRT高级(1)-概述
目录 前言1. tensorRT高级概述总结 前言 杜老师推出的 tensorRT从零起步高性能部署 课程,之前有看过一遍,但是没有做笔记,很多东西也忘了。这次重新撸一遍,顺便记记笔记。 本次课程学习 tensorRT 高级-概述 课程大纲可看下面的思维…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
微服务商城-商品微服务
数据表 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 商…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
