优先级队列priority_queue以及仿函数的使用
目录
- 优先级队列priority_queue
- priority_queue的模拟实现
- 仿函数
优先级队列priority_queue
优先级队列priority_queue是一种容器适配器,根据严格的弱排序标准,它默认第一个元素总是它所包含的元素中最大的
优先级队列默认使用vector作为底层存储数据的容器,在vector上又使用了堆排序的算法对数据进行排序,所以priority_queue
就是堆。注意:priority_queue默认情况下是大堆
priority_queue
是存在<queue>
文件中,要使用只需要包queue
文件就可以
所以以后有需要用到堆的位置,我们就不用手动实现一个堆了,可以直接使用
priority_queue
就可以
下面是优先级队列的定义:
template <class T, class Container = vector<T>,class Compare = less<typename Container::value_type> > class priority_queue;
第一个模板参数是放在适配器容器内元素的类型
第二个模板参数是适配器,默认为vector
第三个模板参数是一个仿函数,默认是less,为了保证默认是大堆
函数 | 接口说明 |
---|---|
priority_queue() | 构造一个空的优先级队列 |
priority_queue (InputIterator first, InputIterator last) | 用[first,last)迭代器区间构造一个优先级队列 |
empty() | 判空 |
top( ) | 返回优先级队列中最大(最小元素),即堆顶元素 |
push(x) | 在优先级队列中插入元素x |
pop() | 删除优先级队列中最大(最小)元素,即堆顶元素 |
下面我们使用优先级队列尝试一下:
void test1()
{priority_queue<int> pq;pq.push(1);pq.push(6);pq.push(9);pq.push(3);pq.push(0);pq.push(2);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}//输出 9 6 3 2 1 0 cout << endl;
}
如果我们先实现一个小堆,只需要改变第三个模板参数就可以,让第三个模板参数为greater<T>
,因为我们指定了第三个模板参数,所以我们还需手动显式传第二个模板参数
下面我们实现一个小堆的priority_queue
:
void test1()
{priority_queue<int,vector<int>,greater<int>> pq;pq.push(1);pq.push(6);pq.push(9);pq.push(3);pq.push(0);pq.push(2);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}//输出 0 1 2 3 6 9cout << endl;
}
priority_queue的模拟实现
因为优先级队列的底层是堆排序,所以我们先完成堆排序中的向下调整,和向上调整
void AdjustDown(int parent)
{Compare com;size_t child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child]<_con[child + 1]){child++;}if (_con[parent]< _con[child]){std::swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}void AdjustUp(int child)
{Compare com;int parent = (child - 1) / 2;while (parent >= 0){if (_con[parent]< _con[child]){std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}
push函数,就是,先向底层适配器中插入一个元素,然后再调用向上调整法
void push(const T& t)
{_con.push_back(t);AdjustUp(_con.size() - 1);}
pop函数,先把适配器中首元素和尾元素交换,然后删除尾元素,再调用向下调整法
void pop()
{std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);
}
还有几个实现起来很简单的函数:
bool empty()
{return _con.empty();
}const T& top()
{return _con[0];
}size_t size()
{return _con.size();
}
当前完整代码:
namespace my_priority_queue
{template<class T, class Container = std::vector<T>>class priority_queue{private:void AdjustDown(int parent){size_t child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child]<_con[child + 1]){child++;}if (_con[parent]< _con[child]){std::swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}}void AdjustUp(int child){int parent = (child - 1) / 2;while (parent >= 0){if (_con[parent]< _con[child]){std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}public: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);}}void push(const T& t){_con.push_back(t);AdjustUp(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}bool empty(){return _con.empty();}const T& top(){return _con[0];}size_t size(){return _con.size();}private:Container _con;};
}
此时,我们已经实现了一个大堆的优先级队列
那么怎么实现小堆的优先级队列呢?当前我们只能去修改向下调整和向上调整中比较大小的部分:
这其实挺麻烦的,有没有什么方法可以使大堆和小堆的优先级队列可以秒切换呢?
答案就是:可以使用仿函数
仿函数
仿函数也叫函数对象,这个类的对象可以像函数一样使用,使一个类的使用看上去像一个函数
其实现就是类中实现一个operator()
,有了对括号的重载,就可以让这个类的对象像函数一样使用
下面就是一个仿函数:
class IntLess
{
public:bool operator()(int x,int y){return x < y;}};
怎么使用仿函数呢?毕竟仿函数是一个类,所以我们使用时需要先实例化一个对象出来
然后将这个对象像使用函数一样使用
在对象后面加上()
,该传参就传参
void test2()
{IntLess LessFunc;cout<<LessFunc(1,2)<<endl;//仿函数的使用
}
LessFunc(1,2)
会被处理成:LessFunc.operator()(1,2)
接下来,用仿函数完善模拟实现的优先级队列
template<class T>
struct Less//首字母大写,为了与库中的less区分
{bool operator()(const T& t1, const T& t2){return t1 < t2;}
};template<class T>
struct Greater
{bool operator()(const T& t1, const T& t2){return t1 > t2;}
};
首先,在模板声明中加一个参数:
template<class T,class Container = std::vector<T>,class Compare = Less<T>>
然后,然后将向上调整和向下调整中大小判断部分改为仿函数
void AdjustDown(int parent)
{Compare com;//仿函数使用前,实例化出一个对象size_t child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}void AdjustUp(int child)
{Compare com;//仿函数使用前,实例化出一个对象int parent = (child - 1) / 2;while (parent >= 0){if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}
相关文章:

优先级队列priority_queue以及仿函数的使用
目录 优先级队列priority_queuepriority_queue的模拟实现仿函数 优先级队列priority_queue 优先级队列priority_queue是一种容器适配器,根据严格的弱排序标准,它默认第一个元素总是它所包含的元素中最大的 优先级队列默认使用vector作为底层存储数据的…...

java+ssm+mysql水费管理系统
项目介绍: 使用javassmmysql开发的用户水费管理系统,系统包含超级管理员,系统管理员、用户角色,功能如下: 超级管理员:管理员管理、用户管理、用水管理(用水记录、缴费提醒)、水费…...

搭建最简单的SpringBoot项目
1、创建maven项目 2、引入父pom <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.7.15</version> </parent> 3、引入springboot-web依赖 <dependency…...
Windows系统手动重新生成性能计数器
症状 使用性能监视器工具时,某些计数器可能缺失或不包含计数器数据。 性能计数器库可能已损坏,需要重新生成。 应用程序日志中可能会出现以下错误: Log Name: Application Source: Microsoft-Windows-IIS-W3SVC-PerfCounters Event ID…...
go elsaticsearch demo
安装 // elasticsearch sdk go get -u github.com/elastic/go-elasticsearch/v7 //操作json go get "github.com/tidwall/gjson" go get "github.com/aquasecurity/esquery"demo package esexampleimport ("bytes""context""en…...

小游戏分发平台如何以技术拓流?
2023年,小游戏的发展将受到多方面的影响,例如新技术的引入、参与小游戏的新玩家以及游戏市场的激烈竞争等。首先,新技术如虚拟现实(VR)、增强现实(AR)和机器人技术都可以带来新颖的游戏体验。其…...

力扣|找出和所对应的两数的下标
从零开始刷力扣(bushi 题目放在这: 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值target的两个整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一…...

使用命令行创建仓库
如果你还没有任何代码,可以通过命令行工具创建一个全新的Git仓库并初始化到本项目仓库中。 git clone https://e.coding.net/***/neurosens.git cd neurosens echo "# neurosens" >> README.md git add README.md git commit -m "first commi…...

ESLint 中的“ space-before-function-paren ”相关报错及其解决方案
ESLint 中的“ space-before-function-paren ”相关报错及其解决方案 出现的问题及其报错: 在 VScode 中,在使用带有 ESLint 工具的项目中,保存会发现报错,并且修改好代码格式后,保存会发现代码格式依然出现问题&…...

docker常用中间件安装
文章目录 1、前言2、中间件安装2.1、mysql2.2、gitlab容器2.3、nacos2.4、redis2.5、xxljob2.6、zipkin2.7、sentinel2.8、seata2.8.1、获取镜像2.8.2、运行容器并获取配置 2.9、rockerMQ2.9.1、rockerMQ-namesrv2.9.2、rockerMQ-broker2.9.3、rockerMQ-console 2.10、jenkins2…...
Camunda 7.x 系列【44】修改流程实例
有道无术,术尚可求,有术无道,止于术。 本系列Spring Boot 版本 2.7.9 本系列Camunda 版本 7.19.0 源码地址:https://gitee.com/pearl-organization/camunda-study-demo 文章目录 1. 概述2. 案例演示2.1 回退2.2 子流程2.3 多实例加签1. 概述 流程模型中,执行活动需要按…...

无频闪护眼灯哪个好?什么是无频闪
随着科技的不断发展,工作时使用电子设备越来越普遍,如何保护我们的眼睛不受蓝光、频闪等危害就变得极其重要了。护眼台灯,顾名思义就是保护眼睛的台灯,其工作原理是在光源处使用特殊的防蓝光灯珠,并通过控制电流的稳定性来达到防频…...

css网格布局
css网格布局 常用属性 display: grid; //开启网格grid-template-columns: 2fr 1fr 1fr 1fr 1fr; //设置多少列每列宽度grid-gap: 10px; // 设置表格之间间距grid-template-rows: 50px 50px 50px 50px; // 设置多少行 每行的高度grid-column : 1 //占据位置 占据1格grid-colu…...
Hadoop -HDFS常用操作指令
1.启动HDFS hadoop/sbin/start-dfs.sh2.关闭 HDFS hadoop/sbin/stop-dfs.sh3. 在HDFS中创建文件夹 #老版本 hadoop fs -mkdir -p path #新版本 hadoop dfs -mkdir -p path4.查看指定目录下内容 hadoop fs -ls [-h] [-R] path hadoop dfs -ls [-h] [-R] ptahpath 指定…...
代码随想录二刷day11
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、力扣20. 有效的括号二、力扣1047. 删除字符串中的所有相邻重复项三、力扣150. 逆波兰表达式求值 前言 一、力扣20. 有效的括号 class Solution {public bo…...

系统架构技能之设计模式-工厂模式
一、开篇 本文主要是讲述设计模式中最经典的创建型模式-工厂模式,本文将会从以下几点对工厂模式进行阐述。 本文将会从上面的四个方面进行详细的讲解和说明,当然会的朋友可以之处我的不足之处,不会的朋友也请我们能够相互学习讨论。 二、摘…...

Docker的基本组成和安装
Docker的基本组成 镜像(image): docker镜像就好比是一个模板,可以通过这个模板来创建容器服务,tomcat镜像 > run > tomcat01容器(提供服务) 通过这个镜像可以创建多个容器(最…...

【python爬虫】15.Scrapy框架实战(热门职位爬取)
文章目录 前言明确目标分析过程企业排行榜的公司信息公司详情页面的招聘信息 代码实现创建项目定义item 创建和编写爬虫文件存储文件修改设置 代码实操总结 前言 上一关,我们学习了Scrapy框架,知道了Scrapy爬虫公司的结构和工作原理。 在Scrapy爬虫公司…...

Apinto 网关 V0.14 版本发布,6 大插件更新!
大家好! 距离上次更新已经过去一段时间了,这段日子里我们一直在酝酿新的功能,本次的迭代将给大家带来 6 大插件的更新~一起来看看有哪些变化吧! 新特性 1. 新增 额外参数v2 插件,支持对转发参数进行加密、拼接等操作…...

突破销售瓶颈:亚马逊卖家如何借力TikTok网红营销?
随着社交媒体的崛起,营销方式也在不断变革。TikTok作为一款风靡全球的短视频平台,吸引了数以亿计的用户,成为了品牌宣传和销售的新热点。对于亚马逊卖家而言,通过合理运用TikTok网红营销策略,可以有效提升产品的曝光度…...

网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...

企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...

GraphQL 实战篇:Apollo Client 配置与缓存
GraphQL 实战篇:Apollo Client 配置与缓存 上一篇:GraphQL 入门篇:基础查询语法 依旧和上一篇的笔记一样,主实操,没啥过多的细节讲解,代码具体在: https://github.com/GoldenaArcher/graphql…...

pgsql:还原数据库后出现重复序列导致“more than one owned sequence found“报错问题的解决
问题: pgsql数据库通过备份数据库文件进行还原时,如果表中有自增序列,还原后可能会出现重复的序列,此时若向表中插入新行时会出现“more than one owned sequence found”的报错提示。 点击菜单“其它”-》“序列”,…...

工厂方法模式和抽象工厂方法模式的battle
1.案例直接上手 在这个案例里面,我们会实现这个普通的工厂方法,并且对比这个普通工厂方法和我们直接创建对象的差别在哪里,为什么需要一个工厂: 下面的这个是我们的这个案例里面涉及到的接口和对应的实现类: 两个发…...

claude3.7高阶玩法,生成系统架构图,国内直接使用
文章目录 零、前言一、操作指南操作指导 二、提示词模板三、实战图书管理系统通过4o模型生成系统描述通过claude3.7生成系统架构图svg代码转换成图片 在线考试系统通过4o模型生成系统描述通过claude3.7生成系统架构图svg代码转换成图片 四、感受 零、前言 现在很多AI大模型可以…...