Priority_Queue 的使用和模拟

目录
一·基本的介绍

优先队列是一种容器适配器;他的第一个元素总是他包含所有元素里面最大的一个

他的底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。
这个底层容器应该可以通过随机访问迭 代器,并支持以下操作:
empty():检测容器是否为空
size():返回容器中有效元素个数
front():返回容器中第一个元素的引用
push_back():在容器尾部插入元素
pop_back():删除容器尾部元素

优先队列里面的“优先”指的是:进行容器遍历访问 的时候优先访问顶部的元素

二. 常用接口的介绍 
1.构造函数

2. void push(const T&val ) 

3. void pop()

 4. const T& top( )

 

 接口的简单使用:

 通过对成员接口的了解,我们可以推测优先队列的底层结构可能是一个

三· 模拟实现
1.仿函数

第一个参数用到的就是仿函数。

仿函数是对 opertaor() 的一个重载

2.仿函数使用
2.1  指定进行降序的输出
2.2 指定进行升序的输出 

2.3 仿函数的调用 

分析:

Less <Date> l2,编译器进行实例化的时候,模板参数T 实例化为 Date 类型,从而生成一份

bool operator() (Date left,Date right)的函数,只不过使用模板,咱们程序员省了此步骤。 

3.priority_queue 类的模拟

一般默认Container 的类型是  vector<T>

为什么默认使用 vector 作为优先队列的底层容器?而不用list这个容器

1) 优先队列支持快速的访问此队列里面的最大或者最小元素;因此底层通常借助堆这一结构实

现,堆是一个特殊的完全二叉树

2)vector 提供了动态大小数组的功能,内部是一段连续的内存,因此在访问元素的时候,大大提

高了效率

3)list 相比较vector 而言,内存是不连续的,在进行元素访问的时候,需要对指针进行一系列操

作,因此效率不如vector

4 push() 模拟

因为需要随时保证访问的第一个元素是最大的或是最小的,这里需模拟建大堆和建小堆的一系列操

有关对堆进行上调和下调的相关细节的实现,可以康康下面博客

 建堆的相关调整

4.1 上调算法
  void adjust_up(int child) //从孩子节点开始{Compare com;int parent = (child - 1 ) / 2;//默认根节点下标从0开始while (child > 0){if (_c[parent] < _c[child]) //对象直接比较//if(com(_c[parent] , _c[child]))  // _com(_c[parent] , _c[child] 相当于回调仿函数模板,可以把_com 想象成函数指针,仿函数模板:替代函数指针{std::swap(_c[parent], _c[child]);child = parent;parent = (child - 1) / 2;}elsebreak;}}
4.2 push ()实现
  void push(const T& x){_c.push_back(x);// 上调:建大堆adjust_up(_c.size()-1);//需要把插入当前数据所在的位置传过去}
5.pop()模拟
5.1 下调算法
        void adjust_down(int parent) //向下调整从父节点开始{Compare com;int child = 2 * parent + 1;while ((size_t)child < (_c.size() )){if ((size_t)child + 1 < (_c.size() ) && _c[child + 1] > _c[child]) // _c[child + 1] > _c[child] 这里直接就是对象的大小比较,可以使用仿函数进行大小比较child++;//更新为最大的孩子节点//if (_c[child] > _c[parent] )if (com( _c[parent], _c[child]) ) //使用仿函数模板{std::swap(_c[child], _c[parent]);parent = child;child = 2 * parent + 1;}elsebreak;}}
5.2 pop()实现
        void pop() {//堆的删除:堆顶与堆尾交换在进行大堆的调整std::swap(_c[0], _c[_c.size() - 1]);_c.pop_back();adjust_down(0);}
6. top()模拟
        T& top(){return _c[0];}
7.size()

8. empty()

9. 完整代码实现 
#pragma once
#include<vector>
namespace y
{//仿函数模板//就是对 () 进行重载template<class T, class Container = vector<T>,class Compare = Less<T>>  //注意:Compare 只是一个模板类型,实例化的时候,会变成指定类型class priority_queue{public:priority_queue(){}template <class InputIterator>priority_queue(InputIterator first, InputIterator last):_c(first,last){//建议使用下调时间复杂度 O(N)//必须是有序,所有一开始传i = (_c.size() - 1 -1)/2 对应最后一个父节点for (int i = (_c.size() - 1 -1)/2; i >= 0; --i){adjust_down(i);}}bool empty() const{return _c.empty();}size_t size() const{return _c.size();}void adjust_down(int parent) //向下调整从父节点开始{Compare com;int child = 2 * parent + 1;while ((size_t)child < (_c.size() )){if ((size_t)child + 1 < (_c.size() ) //&& _c[child + 1] > _c[child]) // _c[child + 1] > _c[child] 这里直接就是对象的大小比较,可以使用仿函数进行大小比较&& com(_c[child], _c[child+1]))// 建大堆child++;//更新为最大的孩子节点//if (_c[child] > _c[parent] )if (com( _c[parent], _c[child]) ) //使用仿函数模板{std::swap(_c[child], _c[parent]);parent = child;child = 2 * parent + 1;}elsebreak;}}void adjust_up(int child) //从孩子节点开始{Compare com;int parent = (child - 1 ) / 2;//默认根节点下标从0开始while (child > 0){//if (_c[parent] < _c[child]) //对象直接比较if(com(_c[parent] , _c[child]))  // _com(_c[parent] , _c[child] 相当于回调仿函数模板,可以把_com 想象成函数指针,仿函数模板:替代函数指针{std::swap(_c[parent], _c[child]);child = parent;parent = (child - 1) / 2;}elsebreak;}}void pop() {//堆的删除:堆顶与堆尾交换在进行大堆的调整std::swap(_c[0], _c[_c.size() - 1]);_c.pop_back();adjust_down(0);}void push(const T& x){_c.push_back(x);// 上调:建大堆adjust_up(_c.size()-1);//需要把插入当前数据所在的位置传过去}T& top(){return _c[0];}private:Container _c;//表示底层的容器//Compare _com;//类似于函数指针};
}

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

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

相关文章

【Java】—— Java面向对象进阶:Java银行账户管理系统设计与实现

目录 1. 账户类&#xff08;Account&#xff09; 2. 客户类&#xff08;Customer&#xff09; 3. 银行类&#xff08;Bank&#xff09; 4. 测试类&#xff08;BankTest&#xff09; 运行结果 在今天的博文中&#xff0c;我们将一起探讨一个简单的Java银行账户管理系统的设…

前端Vue使用AES的GCM模式加密

文章目录 前端加密测试Java加解密代码 写了个新的前端项目&#xff0c;公司要求&#xff0c;账号密码这些必须是加密传输的&#xff1b;后端使用了GCM模式加密&#xff0c;前端是复制的一个以前项目的代码&#xff0c;原来是有写加密的&#xff0c;使用的是CryptoJS组件CTR模式…

2024-8-28作业C++/QT

代码&#xff1a; #include <iostream> #include <cstring> #include <array> #include <iomanip> using namespace std; int main() { //array<char,128> a; //array<char,128>::iterator iter; string str; getline(c…

YOLO | YOLO目标检测算法(基础入门)

github&#xff1a;https://github.com/MichaelBeechan CSDN&#xff1a;https://blog.csdn.net/u011344545 YOLO目标检测算法 深度学习经典检测方法1、两阶段&#xff08;Two-stage&#xff09;2、单阶段&#xff08;One-stage&#xff09; 深度学习经典检测方法 1、两阶段&a…

jenkins发布文件到远程服务器

jenkins安装 安装教程 后台启动脚本 创建脚本&#xff1a;start_jenkins.sh ls for pid in $(ps -ef|grep jenkins.war|grep -v grep|cut -c 10-16); doecho $pid;kill -9 $pid; done;nohup java -Djava.awt.headlesstrue -jar /usr/local/jenkins/jenkins.war --webroot/…

游戏分享网站|基于SprinBoot+vue的游戏分享网站系统(源码+数据库+文档)

游戏分享网站 目录 基于SprinBootvue的游戏分享网站 一、前言 二、系统设计 三、系统功能设计 5.1系统功能模块 5.2后台登录 5.2.1管理员功能模块 5.2.2用户功能模块 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#x…

SpringCloud乐尚代驾学习笔记:环境搭建(二)

文章目录 1、前端环境1.1、注册微信开发者账号1.2、开通服务与插件1.3、微信开发者工具使用 2、服务器端环境2.1、安装mysql2.2、安装rabbitmq2.3、安装redis2.4、安装nacos2.5、安装minio 3、导入初始化项目 1、前端环境 1.1、注册微信开发者账号 虽然开发微信小程序可以使用…

牛客NC313 两个数组的交集 C++

牛客NC313 两个数组的交集 C 思路&#x1f914;&#xff1a; 用哈希表存储第一个数组&#xff0c;再和第二个数组对比&#xff0c;对比成功就添加到新的数组中&#xff0c;之后将哈希表的该位置变为false&#xff0c;防止重复添加。这里数据范围仅有1000&#xff0c;所以我们可…

nginx转发接口地址【非常实用】

使用场景 由于客户的需求是要访问一个外网接口 比如http://58.20.57.190:6652 实例 http://58.20.57.190:6652//uploadBasePatient?Barcode1000000073&customerCode1 比如外网才能访问&#xff0c;科室电脑是访问不了外网的 我们就需要中间在一个既有外网又有内网的前置…

少儿编程入门,Scratch、Python与C++,谁能成为孩子的首选语言?

编程已不再是专业人士的专利&#xff0c;而是成为了一项基本技能。对于孩子们来说&#xff0c;学习编程不仅能提高逻辑思维能力&#xff0c;还能为他们的未来职业生涯打下坚实基础。那么问题来了&#xff0c;面对Scratch、Python和C这三门编程语言&#xff0c;究竟哪一款更适合…

Datawhale AI夏令营

一、物体检测算法 物体检测算法主要分为两类&#xff1a;One-Stage&#xff08;一阶段&#xff09;和Two-Stage&#xff08;两阶段&#xff09;模型。 二、One-Stage目标检测算法 定义&#xff1a;One-Stage目标检测算法是一种直接在图像上进行目标检测的方法&#xff0c;无…

Docker原理及实例

目录 一 Docker简介及部署方法 1.1 Docker简介 1.1.1 什么是docker&#xff1f; 1.1.2 docker在企业中的应用场景 1.1.3 docker与虚拟化的对比 1.1.4 docker的优势 2 部署docker 2.1 容器工作方法 2.2 部署第一个容器 2.2.1 配置软件仓库 2.2.2 安装docker-ce并启动服…

8月28日

思维导图 作业&#xff1a; 使用C手动封装一个顺序表&#xff0c;包含成员数组一个&#xff0c;成员变量N个 代码&#xff1a; #include <iostream>using namespace std;using datatype int; #define MAX 30struct SeqList {private:datatype *data;int size 0;int l…

SpringBoot3与AOP完美结合:轻松追踪用户操作,实现精准日志记录

程序员必备宝典https://tmxkj.top/#/ 1.pom文件 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-aop</artifactId></dependency><dependency><groupId>com.alibaba</groupId&g…

Spring八股文

重点 描述一下bean的生命周期 简述版 调用构造器 或者是通过工厂的方式创建Bean对象给bean对象的属性注入值调用初始化方法&#xff0c;进行初始化&#xff0c; 初始化方法是通过init-method来指定的.使用IOC容器关闭时&#xff0c; 销毁Bean对象 详细&#xff1a; 1. 实例化 …

Qt QCustomPlot画色阶图

工作中用到QCustomPlot画曲线图和色阶图&#xff0c;并且在色阶图上添加文字&#xff0c;圆圈或者几条线段画一些图形&#xff0c;这里写个简单的例子把这几个功能记录一下&#xff0c;代码在这里&#xff1a; https://download.csdn.net/download/Sakuya__/89681279https://…

ggml 简介

ggml是一个用 C 和 C 编写、专注于 Transformer 架构模型推理的机器学习库。该项目完全开源&#xff0c;处于活跃的开发阶段&#xff0c;开发社区也在不断壮大。ggml 和 PyTorch、TensorFlow 等机器学习库比较相似&#xff0c;但由于目前处于开发的早期阶段&#xff0c;一些底层…

『功能项目』怪物受击后显示受击状态UI【12】

本专栏每10章会做一次项目优化&#xff0c;但不影响具体功能 我们可以打开优化前的项目10也可以打开优化后的项目11 双击King或者怪物熊预制体 - 进入预制体空间后创建一个Image改名为StateUI01 代表第一个受击状态 修改Canvas的渲染模式 - 改为世界WorldSpace 调节Image&…

3分钟千人被裁,IBM中国 “灭霸式“裁员背后原因?

2024年8月23日&#xff0c;IMB即有员工传出“无法访问系统”&#xff0c;“无法连接到公司网络”的消息&#xff0c;后续传出裁员的传闻。 图片来源网络 2024年8月26日周一&#xff0c;IBM召开3分钟的会议&#xff0c;宣布彻底关闭IBM中国研发部门&#xff0c;之后直接切断会议…

【Go高性能】测试(单元测试、基准测试)

Go测试 一、分类1. 单元测试2. 基准测试 二、基准测试1. 介绍2. 基准测试基本原则3. 使用testing包构建基准测试3.1 执行基准测试3.2 基准测试工作原理3.3 改进基准测试的准确性3.3.1 -benchtime3.3.2 -count3.3.3 -cpu 4. 使用benchstat工具比较基准测试(可跳过&#xff09;4.…