C++初阶(十六)优先级队列

文章目录
- 一、priority_queue的介绍和使用
- 1、priority_queue的介绍
- 2、priority_queue的使用
- 二、priority_queue的模拟实现
- 1、无仿函数
- 2、带仿函数
一、priority_queue的介绍和使用
1、priority_queue的介绍
- 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
- 此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元
素)。 - 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特
定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。 - 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭
代器访问,并支持以下操作:
empty():检测容器是否为空
size():返回容器中有效元素个数
front():返回容器中第一个元素的引用
push_back():在容器尾部插入元素
pop_back():删除容器尾部元素 - 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指
定容器类,则使用vector。 - 需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数
make_heap、push_heap和pop_heap来自动完成此操作。
2、priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成
堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。注意:
默认情况下priority_queue是大堆。
- 默认情况下,priority_queue是大堆

- 如果要建小堆,需要改变条件

- 如果在priority_queue中放自定义类型的数据,用户需要在自定义类型中提供> 或者< 的重载。
class Date
{
public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}
private:int _year;int _month;int _day;
};
void TestPriorityQueue()
{// 大堆,需要用户在自定义类型中提供<的重载priority_queue<Date> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout << q1.top() << endl;// 如果要创建小堆,需要用户提供>的重载priority_queue<Date, vector<Date>, greater<Date>> q2;q2.push(Date(2018, 10, 29));q2.push(Date(2018, 10, 28));q2.push(Date(2018, 10, 30));cout << q2.top() << endl;}
二、priority_queue的模拟实现
1、无仿函数
namespace bit
{template<class T , class Container =vector<int>>class priority_queue{public:void adjust_up(int child){int parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(int parent){int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && _con[child + 1] > _con[child]){++child;}if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}const T& top(){return _con[0];}private:Container _con;};
}
2、带仿函数
namespace bit
{template<class T , class Container =vector<int>,class Compare=Less<T>>class priority_queue{public:void adjust_up(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(int parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size()&& com(_con[child], _con[child + 1])){++child;}if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}const T& top(){return _con[0];}private:Container _con;};}int main()
{bit::priority_queue<int,vector<int>,Less<int>> v;v.push(1);v.push(9);v.push(8);while (!v.empty()){cout << v.top() << " ";v.pop();}return 0;
}
相关文章:
C++初阶(十六)优先级队列
📘北尘_:个人主页 🌎个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上,不忘来时的初心 文章目录 一、priority_queue的介绍和使用1、priority_queue的介绍2、priority_queue的使用 二、priori…...
深入探索C语言中的二叉树:数据结构之旅
引言 在计算机科学领域,数据结构是基础中的基础。在众多数据结构中,二叉树因其在各种操作中的高效性而脱颖而出。二叉树是一种特殊的树形结构,每个节点最多有两个子节点:左子节点和右子节点。这种结构使得搜索、插入、删除等操作…...
如何发现服务器被入侵了,服务器被入侵了该如何处理?
作为现代社会的重要基础设施之一,服务器的安全性备受关注。服务器被侵入可能导致严重的数据泄露、系统瘫痪等问题,因此及时排查服务器是否被侵入,成为了保障信息安全的重要环节。小德将给大家介绍服务器是否被侵入的排查方案,并采…...
CSDN一键注释功能
这是什么牛逼哄哄的功能 看这里: 然后: 再试一个: 输出结果是?package yuyi03.interview;/*** ClassName: InterviewTest2* Package: yuyi03.interview* Description:** Author 雨翼轻尘* Create 2023/12/14 0014 0:08*/ publ…...
基于JAVA的校园电子商城系统论文
摘 要 网络技术和计算机技术发展至今,已经拥有了深厚的理论基础,并在现实中进行了充分运用,尤其是基于计算机运行的软件更是受到各界的关注。加上现在人们已经步入信息时代,所以对于信息的宣传和管理就很关键。因此校园购物信息的…...
直播传媒公司网站搭建作用如何
直播已然成为抖快等平台的主要生态之一,近些年主播也成为了一种新行业,相关的mcn机构直播传播公司等也时有开业,以旗下主播带来高盈利,而在实际运作中也有一些痛点难题: 1、机构宣传展示难 不少散主播往往会选择合作…...
数据结构与算法-动态规划-机器人达到指定位置方法数
机器人达到指定位置方法数 来自左程云老师书中的一道题 【题目】 假设有排成一行的 N 个位置,记为 1~N,N 一定大于或等于 2。开始时机器人在其中的 M 位置上(M 一定是 1~N 中的一个),机器人可以往左走或…...
K8S学习指南(2)-docker的基本使用
文章目录 引言安装 DockerDocker 基本概念1. 镜像(Images)示例:拉取并运行一个 Nginx 镜像 2. 容器(Containers)示例:查看运行中的容器 3. 仓库(Repository)示例:推送镜像…...
java 执行linux 命令
文章目录 前言一、linux命令执行二、使用步骤三、踩坑 前言 java 执行linux 命令; 本文模拟复制linux文件到指定文件夹后打zip包后返回zip名称,提供给下载接口下载zip; 一、linux命令执行 linux命令执行Process process Runtime.getRunti…...
ubuntu将本机的wifi网络通过网线分享给另一台机器(用于没有有线网络,重装系统后无wifi驱动或者另一台设备没有wifi网卡)
1.将两台机器通过网线连接 2.在pci ethernet中设置选择另一台机器的mac address,ipv4中选择share to other computer,另一台机器上设置为动态ip,连接上之后另一台机器即可上网。...
Docker + Jenkins + Gitee 自动化部署项目
1.简介 各位看官老爷,本文为Jenkins实战,注重实际过程,阅读完会有以下收获: 了解如何使用Docker安装Jenkins了解如何使用Jenkins部署maven项目了解如何使用JenkinsGitee实现自动化部署 2.Jenkins介绍 相信,正在读这…...
ChatGPT 应用开发(一)ChatGPT OpenAI API 免代理调用方式(通过 Cloudflare 的 AI Gateway)
前言 开发 ChatGPT 应用,我觉得最前置的点就是能使用 ChatGPT API 接口。首先我自己要能成功访问,这没问题,会魔法就可以本地调用。 那用户如何调用到我的应用 API 呢,我的理解是通过用户能访问到的中转服务器向 OpenAI 发起访问…...
【TC3xx】GETH
目录 一、RGMII 二、SMI接口 三、TC3xx MCAL 3.1 MCU 3.2 Port 3.3 DMA 3.4 中断配置 3.5 ETH 3.6 集成 一、RGMII TC3xx支持MII/RMII/RGMII三种以太网数据通信接口。其中RGMII经常用于MAC和MAC之间,或MAC与PHY之间的通信,RGMII的带宽可以是10M…...
不需要联网的ocr项目
地址 GitHub - plantree/ocr-pwa: A simple PWA for OCR, based on Tesseract. 协议 mit 界面 推荐理由 可以离线使用,隐私安全...
【Git使用总结】
Git使用总结 随着软件开发和团队协作的日益重要,Git作为一种强大的版本控制系统,已经成为了开发人员不可或缺的工具。本文将对Git的使用进行总结,以帮助读者更好地掌握Git的用法和技巧。 一、Git的基本概念 在开始使用Git之前,…...
仿照MyBatis手写一个持久层框架学习
首先数据准备,创建MySQL数据库mybatis,创建表并插入数据。 DROP TABLE IF EXISTS user_t; CREATE TABLE user_t ( id INT PRIMARY KEY, username VARCHAR ( 128 ) ); INSERT INTO user_t VALUES(1,Tom); INSERT INTO user_t VALUES(2,Jerry);JDBC API允…...
关东升老师极简系列丛书(由清华大学出版社出版)
极简系列丛书,编程学习新体验 在这个科技日新月异的时代,编程已经成为了一种必备技能。但是面对各种复杂的编程语言,你是否也曾感到过迷茫和困惑?由清华大学出版社出版的“极简系列丛书”就是为了帮助你解决这个问题。 这套丛书…...
要求CHATGPT高质量回答的艺术:提示工程技术的完整指南—第 27 章:如何避开和绕过所有人工智能内容检测器
要求CHATGPT高质量回答的艺术:提示工程技术的完整指南—第 27 章:如何避开和绕过所有人工智能内容检测器 使用高易错性和突发性方法 与人工智能生成的文本相比,人类写作往往具有更多的突发性,这是由于人类往往比人工智能生成的文…...
JavaWeb笔记之MySQL数据库
#Author 流云 #Version 1.0 一、引言 1.1 现有的数据存储方式有哪些? Java程序存储数据(变量、对象、数组、集合),数据保存在内存中,属于瞬时状态存储。 文件(File)存储数据,保存…...
Amazon CodeWhisperer 开箱初体验
文章作者:Coder9527 科技的进步日新月异,正当人工智能发展如火如荼的时候,各大厂商在“解放”码农的道路上不断创造出各种 Coding 利器,今天在下就带大家开箱体验一个 Coding 利器: Amazon CodeWhisperer。 亚马逊云科…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用
中达瑞和自2005年成立以来,一直在光谱成像领域深度钻研和发展,始终致力于研发高性能、高可靠性的光谱成像相机,为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...
Java后端检查空条件查询
通过抛出运行异常:throw new RuntimeException("请输入查询条件!");BranchWarehouseServiceImpl.java // 查询试剂交易(入库/出库)记录Overridepublic List<BranchWarehouseTransactions> queryForReagent(Branch…...
