【C++入门到精通】C++入门 —— priority_queue(STL)优先队列

阅读导航
- 前言
- 一、priority_queue简介
- 1. 概念
- 2. 特点
- 二、priority_queue使用
- 1. 基本操作
- 2. 底层结构
- 三、priority_queue模拟实现
- ⭕ C++代码
- ⭕priority_queue中的仿函数
- 总结
- 温馨提示
前言
⭕文章绑定了VS平台下std::priority_queue的源码,大家可以下载了解一下😍
前面我们讲了C语言的基础知识,也了解了一些数据结构,并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载,引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ,以及学习了几个STL的结构也相信大家都掌握的不错,接下来博主将会带领大家继续学习有关C++比较重要的知识点—— priority_queue(STL)优先队列。下面话不多说坐稳扶好咱们要开车了😍
一、priority_queue简介
⭕官方文档

1. 概念
priority_queue是C++标准库中的一个容器适配器(container adapter),用于实现优先队列(priority queue)的数据结构。优先队列是一种特殊的队列,其中的元素按照一定的优先级进行排序,每次取出的元素都是优先级最高的。它的底层实现通常使用堆(heap)数据结构。
在C++中,priority_queue模板类定义在<queue>头文件中,可以通过指定元素类型和比较函数来创建不同类型的优先队列。比较函数用于确定元素的优先级,可以是函数指针、函数对象或Lambda表达式。
⭕需要注意的是,默认情况下,priority_queue使用std::less作为比较函数,即元素的优先级按照从大到小的顺序排列。如果需要按照从小到大的顺序排列,可以使用std::greater作为比较函数。
2. 特点
-
优先级排序:
priority_queue中的元素按照一定的优先级进行排序。默认情况下,元素的优先级按照从大到小的顺序排列,也可以通过自定义的比较函数来指定不同的排序方式。 -
自动排序:在插入元素时,
priority_queue会根据元素的优先级自动进行排序。每次插入新元素时,都会将新元素放置在正确的位置上。 -
取出优先级最高元素:
priority_queue提供了一种方便的方式来取出优先级最高的元素。使用top()函数可以访问优先级最高的元素,而使用pop()函数可以将该元素从队列中移除。 -
底层实现采用堆:
priority_queue通常使用堆(heap)数据结构来实现。堆是一种具有特定性质的二叉树,可以高效地插入新元素和取出优先级最高的元素。 -
动态大小:
priority_queue的大小可以根据需要进行动态调整。可以随时插入新元素和删除已有元素,并在必要时自动重新排序。
⭕需要注意的是,priority_queue并不支持直接访问和修改除了优先级最高元素外的其他元素。如果需要对特定元素进行操作,通常需要先将其取出,然后再进行操作,最后再将其放回优先队列中。
二、priority_queue使用
1. 基本操作
- 包含头文件:首先,在使用
priority_queue之前,你需要包含<queue>头文件。
#include <queue>
- 定义容器和比较函数:然后,你需要定义一个
priority_queue对象,并指定元素类型和可选的比较函数(默认为std::less)。
std::priority_queue<int, std::vector<int>, std::less<int>> pq;
上面的示例定义了一个存储整数的优先队列,使用std::less作为比较函数,以便元素按照从大到小的顺序排列。
- 插入元素:你可以使用
push()函数插入元素到priority_queue中。插入的元素会根据其优先级自动进行排序。
pq.push(3);
pq.push(1);
pq.push(4);
pq.push(1);
在上面的示例中,我们依次插入了4个整数到优先队列中。
- 访问和移除元素:你可以使用
top()函数访问优先级最高的元素,使用pop()函数移除优先级最高的元素。
std::cout << pq.top() << std::endl; // 访问优先级最高的元素
pq.pop(); // 移除优先级最高的元素
在上面的示例中,我们先输出了优先级最高的元素,然后将其从队列中移除。
- 检查队列是否为空:你可以使用
empty()函数来检查priority_queue是否为空。
if (pq.empty()) {// 队列为空
} else {// 队列不为空
}
下面的代码,演示了如何使用priority_queue:
#include <queue>
#include <iostream>int main() {std::priority_queue<int, std::vector<int>, std::less<int>> pq;pq.push(3);pq.push(1);pq.push(4);pq.push(1);while (!pq.empty()) {std::cout << pq.top() << " ";pq.pop();}return 0;
}
输出结果为:4 3 1 1
在上面的代码中,我们创建了一个存储整数的优先队列pq,并依次插入了4个元素。然后,我们使用top()函数和pop()函数访问和移除元素,最后使用empty()函数检查队列是否为空。
2. 底层结构
priority_queue的底层通常使用堆(heap)数据结构来实现。堆是一种二叉树的数据结构(堆,数据结构详细介绍链接),具有以下特点:
-
堆结构是一个完全二叉树(Complete Binary Tree),即除了最后一层外,其他层都必须是满的,且最后一层的结点都靠左排列。
-
二叉堆分为最大堆(Max Heap)和最小堆(Min Heap)两种类型。
- 最大堆:每个父节点的值都大于或等于其子节点的值,即根节点的值最大。
- 最小堆:每个父节点的值都小于或等于其子节点的值,即根节点的值最小。
在priority_queue中,默认情况下采用最大堆实现,即优先级最高的元素存储在根节点,根节点的值最大。根据堆的性质,保证了在插入元素时,优先队列会根据元素的优先级进行自动排序,并在取出元素时能够取出优先级最高的元素。

三、priority_queue模拟实现
⭕ C++代码
#pragma once
#include<iostream>
using namespace std;
#include<vector>
namespace yws
{template<class T, class Container = vector<T>, class Compare = std::less<T>>class priority_queue{public:priority_queue(){}template <class Inputinterpreator>priority_queue(Inputinterpreator first, Inputinterpreator last){while (first != last){_con.push_back(*first);++first;}for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i){adjust_down(i);}}void adjust_up(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);}else{break;}child = parent;parent = (child - 1) / 2;}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(size_t 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 = child + 1;}if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);}else{break;}parent = child;child = (parent * 2) + 1;}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
}
⭕priority_queue中的仿函数
在priority_queue中,仿函数用于比较元素的优先级,并根据其返回值确定它们在队列中的位置。默认情况下,priority_queue使用std::less作为仿函数,也就是将元素按照从大到小的顺序进行排序。
你可以使用不同的仿函数来改变元素的排序方式。以下是一些常见的仿函数:
std::less<T>:对于基本数据类型和自定义类型,默认使用<运算符进行比较,按照从大到小的顺序排序。std::greater<T>:对于基本数据类型和自定义类型,默认使用>运算符进行比较,按照从小到大的顺序排序。
除了上述默认提供的仿函数外,你还可以自定义仿函数来实现自定义的元素比较规则。自定义仿函数需要满足严格弱排序(Strict Weak Ordering)的要求,即:
- 比较关系必须是可传递的(transitive):对于任意元素a、b和c,如果a与b比较相等,b与c比较相等,则a与c比较也相等。
- 比较关系不能是部分顺序(partial order):对于任意元素a和b,它们不能同时大于、小于或等于彼此。
- 比较关系必须是可比较的(comparable):比较关系的结果必须对所有元素定义明确的大小关系。
以下这段代码,演示了如何自定义一个仿函数来实现元素的自定义排序方式:
#include <iostream>
#include <queue>
#include <functional>struct Person {std::string name;int age;Person(const std::string& n, int a) : name(n), age(a) {}
};// 自定义仿函数
struct CompareByAge {bool operator()(const Person& p1, const Person& p2) const {return p1.age > p2.age; // 按照年龄从小到大排序}
};int main() {std::priority_queue<Person, std::vector<Person>, CompareByAge> pq;pq.push(Person("Alice", 25));pq.push(Person("Bob", 30));pq.push(Person("Charlie", 20));while (!pq.empty()) {Person p = pq.top();pq.pop();std::cout << p.name << " - " << p.age << std::endl;}return 0;
}
输出结果为:
Charlie - 20
Alice - 25
Bob - 30
在上面的代码中,我们定义了一个名为CompareByAge的结构体,重载了函数调用运算符operator(),按照Person对象的age成员进行比较。然后,我们将CompareByAge作为优先队列的仿函数类型,并插入3个Person对象到优先队列中。最后,我们按照自定义的排序方式依次取出元素并输出。
总结
优先队列是一种特殊的队列,其中存储的元素按照一定的优先级进行排列。在priority_queue中,优先级最高的元素能够快速被访问和删除。
首先,我们介绍了priority_queue的概念和特点。它是基于堆(heap)这种数据结构实现的,通常使用最大堆来进行内部排序。最大堆保证了根节点的值最大,并且任意节点的值大于或等于其子节点的值。这种特性使得优先队列能够高效地访问和删除具有最高优先级的元素。
接着,我们深入探讨了priority_queue的使用方法。基本操作包括插入元素、删除元素、访问元素和检查队列是否为空。
底层结构是priority_queue的关键部分,它通常使用堆来实现。在堆中,通过使用数组的索引来表示节点之间的关系,能够快速定位和操作元素。
最后,我们探讨了在priority_queue中使用的仿函数。仿函数用于确定元素之间的优先级,决定元素在队列中的位置。默认情况下,priority_queue使用std::less仿函数进行比较,对元素进行降序排列。你还可以选择其他仿函数或自定义仿函数来实现不同的排序方式。
温馨提示
感谢您对博主文章的关注与支持!在阅读本篇文章的同时,可以留下您宝贵的意见和反馈。如果您喜欢这篇文章,可以点赞、评论和分享给您的同学,这将对我提供巨大的鼓励和支持。另外,我计划在未来的更新中持续探讨与本文相关的内容。我会为您带来更多关于C++以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新,不要错过任何精彩内容!
再次感谢您的支持和关注。期待与您建立更紧密的互动,共同探索C++、算法和编程的奥秘。祝您生活愉快,排便顺畅!

相关文章:
【C++入门到精通】C++入门 —— priority_queue(STL)优先队列
阅读导航 前言一、priority_queue简介1. 概念2. 特点 二、priority_queue使用1. 基本操作2. 底层结构 三、priority_queue模拟实现⭕ C代码⭕priority_queue中的仿函数 总结温馨提示 前言 ⭕文章绑定了VS平台下std::priority_queue的源码,大家可以下载了解一下&…...
静态代码扫描工具 Sonar 配置及使用
概览 Sonar 是一个用于代码质量管理的开放平台。通过插件机制,Sonar 可以集成不同的测试工具,代码分析工具,以及持续集成工具。与持续集成工具(例如 Hudson/Jenkins 等)不同,Sonar 并不是简单地把不同的代…...
docker 03(docker 容器的数据卷)
一、数据卷的概念和作用 删除后,数据也没了。 不能 数据卷 是宿主机中的一个目录或文件当容器目录和数据卷目录绑定后,对方的修改会立即同步一个数据卷可以被多个容器同时挂载 作用: 容器数据持久化 外部机器和容器间接通信 容器之间数据交换…...
【04】基础知识:typescript中的类
一、es5 对象 1、定义 类(对象) 原型链上的属性和方法会被多个实例共享。构造函数中的属性和方法不会。 // 自定义构造函数 function Person(name, age) {this.name namethis.age agethis.getInfo function() {console.log(${this.name} - ${this.…...
CCClippingNode:在游戏中实现遮罩效果、剪切效果,以涂抹糖霜为例,如何更好的实现涂抹效果,提高用户的游戏体验
CCClippingNode:在游戏中实现遮罩效果、剪切效果,以涂抹糖霜为例,如何更好的实现涂抹效果 设备/引擎:Mac(11.6)/cocos2d-x 开发工具:Xcode(13.0) 开发需求:…...
cuda gdb调试
如果cudaDeviceEnablePeerAccess函数不支持或不起作用,您仍然可以尝试其他方法来实现GPU之间的数据交换和通信。以下是一些替代方法: 通过主机内存进行数据传输: 如果GPU之间的数据交换不是非常频繁,您可以将数据从一个GPU复制到…...
【vim 学习系列文章 5 - cscope 过滤掉某些目录】
文章目录 cscope 过滤目录介绍 cscope 过滤目录介绍 第一步创建自己的cscope脚本~/.local/bin/cscope.sh,如下: function my_cscope() {CODE_PATHpwdecho "$CODE_PATH"echo "start cscope...."if [ ! -f "$CODE_PATH/cscope.…...
实验三 HBase1.2.6安装及配置
系列文章目录 文章目录 系列文章目录前言一、HBase1.2.6的安装二、HBase1.2.6的配置2.1 单机模式配置2.2 伪分布式模式配置 总结参考 前言 在安装HBase1.2.6之前,需要安装好hadoop2.7.6。 本篇文章参考:HBase2.2.2安装和编程实践指南 一、HBase1.2.6的安…...
LightDB sequence支持MAXVALUE最大值与Oracle相同
功能介绍 Oracle数据库在创建sequence的时候可以支持设置maxvalue 为9999999999999999999999999999,这样的SQL在LightDB23.3版本之前都是执行失败的。为了方便Oracle用户迁移到LightDB上,在LightDB23.3版本上,增加了sequence支持maxvalue设置…...
二、Kafka快速入门
目录 2.1 安装部署1、【单机部署】2、【集群部署】 2.2 Kafka命令行操作1、查看topic相关命令参数2、查看当前kafka服务器中的所有Topic3、创建 first topic4、查看 first 主题的详情5、修改分区数(注意:分区数只能增加,不能减少)…...
消息中间件-kafka实战-第五章-kafka重复消费、顺序消费及死信队列
目录 一、参考二、路由规则(分片规则)三、触发重复消费的场景场景一:触发rebalance问题描述可能原因实际影响参数在kafka0.10.1 之前:在kafka0.10.1之后:解决方案 场景二:服务宕机可能原因解决方案 消息幂等性 四、kaf…...
python爬虫9:实战2
python爬虫9:实战2 前言 python实现网络爬虫非常简单,只需要掌握一定的基础知识和一定的库使用技巧即可。本系列目标旨在梳理相关知识点,方便以后复习。 申明 本系列所涉及的代码仅用于个人研究与讨论,并不会对网站产生不好…...
从业务层的代码出发,去排查通用框架代码崩溃的问题
目录 1、问题说明 1.1、Release下崩溃,Debug下很难复现 1.2、用Windbg打开dump文件,发现崩溃在通用的框架代码中 2、进一步分析 2.1、使用IDA查看汇编代码尝试寻找崩溃的线索 2.2、在Windbg中查看相关变量的值 2.3、查看最近代码的修改记录&#…...
LLM预训练大型语言模型Pre-training large language models
在上一个视频中,您被介绍到了生成性AI项目的生命周期。 如您所见,在您开始启动您的生成性AI应用的有趣部分之前,有几个步骤需要完成。一旦您确定了您的用例范围,并确定了您需要LLM在您的应用程序中的工作方式,您的下…...
[Machine Learning] 损失函数和优化过程
文章目录 机器学习算法的目的是找到一个假设来拟合数据。这通过一个优化过程来实现,该过程从预定义的 hypothesis class(假设类)中选择一个假设来最小化目标函数。具体地说,我们想找到 arg min h ∈ H 1 n ∑ i 1 n ℓ ( X i…...
serialVersionUID 有何用途?如果没定义会有什么问题?
序列化是将对象的状态信息转换为可存储或传输的形式的过程。我们都知道,Java 对象是保持在 JVM 的堆内存中的,也就是说,如果 JVM 堆不存在了,那么对象也就跟着消失了。 而序列化提供了一种方案,可以让你在即使 JVM 停机…...
C# OpenCvSharp DNN 二维码增强 超分辨率
效果 项目 代码 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; using OpenCvSharp; using OpenCvSharp.Dnn; using OpenCvSh…...
this.$refs使用方法
深入理解和使用this.$refs——Vue.js的利器 Vue.js是一个流行的JavaScript框架,用于构建交互性强大的用户界面。在Vue.js中,this.$refs是一个强大的特性,允许你直接访问组件中的DOM元素或子组件实例。本教程将带你深入了解this.$refs的使用方…...
Ohio主题 - 创意组合和代理机构WordPress主题
Ohio主题是一个精心制作的多用途、简约、华丽、多功能的组合和创意展示主题,具有敏锐的用户体验,您需要构建一个现代且实用的网站,并开始销售您的产品和服务。它配备了最流行的WordPress页面构建器 WPBakery Page Builder(以前称为…...
mysql 、sql server trigger 触发器
sql server mySQL create trigger 触发器名称 { before | after } [ insert | update | delete ] on 表名 for each row 触发器执行的语句块## 表名: 表示触发器监控的对象 ## before | after : 表示触发的时间,before : 表示在事件之前触发&am…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
SpringAI实战:ChatModel智能对话全解
一、引言:Spring AI 与 Chat Model 的核心价值 🚀 在 Java 生态中集成大模型能力,Spring AI 提供了高效的解决方案 🤖。其中 Chat Model 作为核心交互组件,通过标准化接口简化了与大语言模型(LLM࿰…...
ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]
报错信息:libc.so.6: cannot open shared object file: No such file or directory: #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...
【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...
js 设置3秒后执行
如何在JavaScript中延迟3秒执行操作 在JavaScript中,要设置一个操作在指定延迟后(例如3秒)执行,可以使用 setTimeout 函数。setTimeout 是JavaScript的核心计时器方法,它接受两个参数: 要执行的函数&…...
