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

【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)来表示。堆是一种完全二叉树数据结构,具有以下特点:

  1. 堆是一个完全二叉树,也就是说除了最底层,其他层都必须是完全填满的,最底层的节点依次从左到右填充。
    2.堆中的每个节点的值都大于等于(或小于等于)其子节点的值,这就是所谓的堆序性质。

2.介绍

  1. 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
  2. 此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。
  3. 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类
  4. 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭
    代器访问,并支持以下操作:
    empty():检测容器是否为空
    size():返回容器中有效元素个数
    front():返回容器中第一个元素的引用
    push_back():在容器尾部插入元素
    pop_back():删除容器尾部元素
  5. 标准容器类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++】优先级队列的基本概念以及其模拟实现

文章目录 补充知识&#xff1a;仿函数一、优先级队列&#xff1a;1.引入2.介绍 二、priority_queue的模拟实现1.大体框架2.私有成员函数&#xff1a;1.向下调整&#xff08;AdjustDown&#xff09;2.向上调整&#xff08;AdjustUp&#xff09; 3.公有成员函数1大小&#xff08;…...

TextClamp for Vue3.0(Vue3.0的文本展开收起组件)

呦&#xff01;大家好&#xff0c;好久没有更新博客了&#xff0c;最近实现了一个一直想自己完成的一个东西&#xff0c;就是文本的展开收起组件&#xff0c;以前项目需要用到&#xff0c;自己实现一个又太繁琐&#xff0c;所以那个时候都是用的别人的轮子&#xff0c;现在自己…...

区间预测 | MATLAB实现VAR向量自回归时间序列区间预测

区间预测 | MATLAB实现VAR向量自回归时间序列区间预测 目录 区间预测 | MATLAB实现VAR向量自回归时间序列区间预测预测效果基本介绍程序设计参考资料预测效果 基本介绍 区间预测 | MATLAB实现VAR向量自回归时间序列区间预测 VAR(Vector Autoregression)模型是一种广泛应用于时…...

在 Windows 上搭建 NTP 服务器

文章目录 一、基础环境二、适用场景三、操作步骤四、常用的NTP服务器五、参考资料 版权声明&#xff1a;本文为博主原创文章&#xff0c;于2023年7月30日首发于CSDN&#xff0c;转载请附上原文出处链接和本声明。本文链接&#xff1a;https://blog.csdn.net/u011046671 一、基础…...

应急响应经典案例-FTP 暴力破解

应急响应经典案例-FTP 暴力破解 应急场景日志分析应急处理措施 应急场景 从昨天开始&#xff0c;网站响应速度变得缓慢&#xff0c;网站服务器登录上去非常卡&#xff0c;重启服务器就能保证一段时间的正常访问&#xff0c;网站响应状态时而飞快时而缓慢&#xff0c;多数时间是…...

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启动流程源码&#xff1a; 1、启动SpringBoot启动类SpringbootdemoApplication中的main方法。 SpringBootApplication public class SpringbootdemoApplication {public static void main(String[] args) {SpringApplication.run(SpringbootdemoApplication.class, …...

【Linux】进程轻松入门

目录 一&#xff0c; 冯* 诺依曼体系结构 1&#xff0c;存储结构 ​编辑 二&#xff0c; 操作系统 1&#xff0c;概念 2&#xff0c;设计OS的目的 3&#xff0c;定位 4&#xff0c;如何理解 "管理" 5&#xff0c; 总结 三&#xff0c;进程 1. 概念 那么…...

【使用时空RBF-NN进行非线性系统识别】实现了 RBF、分数 RBF 和时空 RBF 神经网络,用于非线性系统识别研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

Tomcat 安装配置教程及成功后,启动失败报错解决方案

解决方案 我的报错原因是因为我的JDK是1.8的而我的Tomcat是10版本的&#xff0c;可能是因为版本原因吧&#xff0c;我重新装了Tomcat 9就可以启动成功了&#xff01; 简单说下安装的时候需要注意哪些步骤吧 今天我在安装tomcat10的时候&#xff0c;安装成功后&#xff0c;启…...

C#文件操作从入门到精通(2)——查看某个dll中有哪些函数

kernel32.dll中含有ini文件操作使用的函数,我们可以通过VisualStudio自带的dumpbin.exe查看dll所包含的函数,操作步骤如下: 1、找到dumpbin.exe所在的文件夹 我的电脑中安装了VisualStudio2019社区版以及VisualStudio2017Professional,但是我发现VisualStudio2019社区版中…...

二分查找算法(全网最详细代码演示)

二分查找也称 半查找&#xff08;Binary Search&#xff09;&#xff0c;它时一种效率较高的查找方法。但是&#xff0c;折半查找要求线性表必须采用顺序存储结构&#xff0c;而且表中元素按关键字 有序 排列。 注意&#xff1a;使用二分查找的前提是 该数组是有序的。 在实际开…...

draw up a plan

爱情是美好的&#xff0c;却不是唯一的。爱情只是属于个人化的感情。 推荐一篇关于爱情的美文&#xff1a; 在一个小镇上&#xff0c;有一家以制作精美巧克力而闻名的手工巧克力店&#xff0c;名叫“甜蜜之爱”。这家巧克力店是由一位名叫艾玛的年轻女性经营的&#xff0c;她对…...

抖音seo源码开发源代码开发技术分享

一、 抖音SEO源码开发&#xff0c;需要掌握以下技术&#xff1a; 抖音API接口&#xff1a;抖音提供了丰富的API接口&#xff0c;包括用户信息、视频信息、评论信息等。 数据爬取技术&#xff1a;通过抓包分析抖音接口的数据结构&#xff0c;可以使用Python等编程语言编写爬虫程…...

QEMU(Quick Emulator)

QEMU&#xff08;Quick Emulator&#xff09;是一款由法布里斯贝拉等人编写的免费的可执行硬件虚拟化的开源托管虚拟机。它可以通过动态的二进制转换模拟CPU&#xff0c;并提供一组设备模型&#xff0c;使它能够运行多种未修改的客户机OS。QEMU还可以为user-level的进程执行CPU…...

Gateway结合nacos(lb://xxx)无效问题

Gateway结合nacos无效 版本如下&#xff1a; com.alibaba.cloud:spring-cloud-starter-alibaba-nacos-discovery:2021.0.1.0 org.springframework.cloud:spring-cloud-starter-gateway:3.1.1 配置如下&#xff1a; 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( ) - 示例 以下是一个简单的示例&#xff0c;简单说明了此方法的用法- <html><head><title>The jQuery Example</title>…...

Linux vsftp三种模式的简单配置部署

环境&#xff1a;Debian 6.1.27-1kali1 (2023-05-12) vsftpd 安装 --查看是否当前系统是否已安装 apt list --installed | grep vsftpd 没有安装的话&#xff0c;就正常安装 apt-get update apt-get install vsftpd 一、匿名用户模式 分享一些不重要文件&#xff0c;任…...

6.1.tensorRT高级(1)-概述

目录 前言1. tensorRT高级概述总结 前言 杜老师推出的 tensorRT从零起步高性能部署 课程&#xff0c;之前有看过一遍&#xff0c;但是没有做笔记&#xff0c;很多东西也忘了。这次重新撸一遍&#xff0c;顺便记记笔记。 本次课程学习 tensorRT 高级-概述 课程大纲可看下面的思维…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...