【C++ STL】 容器详解：priority_queue 学习

devtools/2025/3/13 9:46:57/

在 C++ STL（标准模板库）中，priority_queue 是 优先队列，它是一种特殊的队列，出队顺序 按照优先级排序，而非 FIFO（先进先出）。底层实现通常基于 堆（heap） 数据结构，因此具有 高效的插入和删除操作。

1. priority_queue 的基本特点

  • 按优先级出队：默认情况下，元素按 大顶堆（最大值优先） 方式存储。
    与普通的队列（queue）不同，priority_queue中的元素并不是按照先进先出（FIFO）的顺序进行处理，而是按照优先级的高低进行处理。默认情况下，priority_queue是一个最大堆，即优先级最高的元素（通常是最大的元素）会最先被取出。

  • 底层结构：基于 堆（heap），通常是 二叉堆。

  • 时间复杂度：插入和删除的时间复杂度均为 O(log n)。

2. priority_queue 的基本用法

2.1 priority_queue 的定义与初始化

priority_queue<T, Container, Compare> pq;//T：存储的元素类型。
//Container：底层容器类型，默认为vector<T>。
//Compare：比较函数对象类型，默认为less<T>，即最大堆。
定义一个存储整数的最大堆：
priority_queue<int> maxHeap;定义一个存储整数的最小堆：
priority_queue<int, vector<int>, greater<int>> minHeap;

#include <iostream>
#include <queue>
using namespace std;int main() {priority_queue<int> pq;// 插入元素pq.push(10);pq.push(30);pq.push(20);// 访问队头（最大值）cout << "队头: " << pq.top() << endl;return 0;
}

输出：

队头: 30

可以看到，最大元素优先出队。

2.2 插入与删除

pq.push(40);  // 插入 40
pq.pop();     // 移除最大值（40）

2.3 访问队头元素(顶部元素）

使用top()方法访问priority_queue中的顶部元素（即优先级最高的元素）：

cout << "队头: " << pq.top() << endl;

2.4 检查队列是否为空

if (pq.empty()) {cout << "队列为空" << endl;
}

2.5 获取队列大小

cout << "队列大小: " << pq.size() << endl;

3. priority_queue 的自定义排序

最小值优先

默认情况下，priority_queue 是 大顶堆，如果需要 小顶堆（最小值优先），可以使用 greater<>：

priority_queue<int, vector<int>, greater<int>> minHeap;

如果需要 自定义排序规则，可以使用结构体或 Lambda 表达式：

struct Compare {bool operator()(int a, int b) {return a > b; // 小值优先}
};
priority_queue<int, vector<int>, Compare> customPQ;

结构体排序示例

如果 priority_queue 需要存储 自定义结构体（如商品、任务等），可以重载 operator< 进行排序。例如：晴问算法--priority_queue-结构体

#include <bits/stdc++.h>
using namespace std;struct Fruit {string name;int price;Fruit(string _name, int _price) { //构造函数name = _name;price = _price;}bool operator<(const Fruit& other) const {return price > other.price; // 价格低的优先出队}
};int main() {priority_queue<Fruit> q;int n;cin >> n;while (n--) {string name;int price;cin >> name >> price;q.push(Fruit(name, price));//将Fruit对象推入优先队列q中}Fruit topFruit = q.top();cout << topFruit.name << " " << topFruit.price;return 0;
}

在这道题目中，我们需要实现一个优先队列来存储不同水果的信息，并根据价格进行排序。具体来说，我们需要定义一个结构体Fruit，并在其中重载<操作符，以便优先队列能够根据价格进行排序。最后，我们需要将水果信息输入到优先队列中，并输出队首水果的名称和价格。 

补充：结构体与构造函数

1. 结构体

结构体可以将多个相同或不同类型的变量组合在一起，语法如下：

struct Point {int x, y;
};

通过上面的写法可以将两个 int 型变量 x 和 y 组合成一个复合类型。对 C++ 来说，Point 就是这个新的复合类型，我们在之后的代码中可以直接使用 Point 来指代这个类型。

但是对 C 语言来说，struct Point 才是新的复合类型，因此在之后的代码中必须使用 struct Point 来指代这个类型。不过这确实有些麻烦，所以常见的做法是在定义结构体之后额外增加一条 typedef 语句，将 struct Point 类型用别名 Point 代替，这样后续代码就可以直接使用 Point 来指代这个结构体类型，会简单许多，示例如下（注意只有 C 语言才需要）：

C

struct Point {int x, y;
};
typedef struct Point Point;

当然我们也可以将上面的两个定义合在一起：

C

typedef struct Point {int x, y;
} Point;

上面这个结构看起来复杂，但其实就是 typdef struct Point {...} Point 的意思，也就是说给结构体类型 struct Point {...} 取了个类型别名 Point，这样后续代码就可以直接使用 Point 这个名字了。

2. 构造函数

构造函数是在结构体内部定义的一种特殊函数，可以用来构造结构体变量，它的 函数名和结构体名相同，并且 没有返回类型。

本题要求构造函数接收两个参数，并把这两个参数分别赋值给结构体内的两个变量，以此来生成一个带有初始值的结构体变量。

下面是题目要求使用的构造函数（函数的参数名使用下划线（例如 _x）只是为了和结构体内部定义的变量（例如 x）区分，也可以叫其他名字）：

C++

Point(int _x, int _y) {x = _x;y = _y;
}

它也可以简写为：

C++

Point(int _x, int _y): x(_x), y(_y) {}

在定义了上面的构造函数之后，我们就可以使用 Point(1, 2) 这种方式来构造带初始值的结构体变量。

而如果不写构造函数的话，默认会生成一个构造函数，这个构造函数没有参数，并且不对结构体内的变量赋初值，这个构造函数是这样的：

C++

Point() {}

这个默认构造函数的作用是定义未被赋初值的结构体变量，例如：

C++

Point p;
Point ps[100];

需要注意，一旦我们自己定义了一个构造函数，就会把上面这个默认构造函数覆盖掉，此时只定义结构体变量而不对其赋初值时不允许的。解决办法也很简单，手动将这个默认构造函数补上即可，因为 一个结构体内是允许同时存在多个构造函数的。

输入示例：

3
Apple 50
Banana 30
Cherry 40

输出：

Banana 30

此代码实现了一个 按价格排序的优先队列，其中 价格最低的水果最先出队。

4. priority_queue 的应用场景

  • 任务调度：优先级最高的任务最先处理。

  • Dijkstra 最短路径算法：用于维护最短路径的候选点。

  • Huffman 编码：构造最优前缀编码树。

5. priority_queue 与 queue、set 的区别

特性priority_queuequeueset
底层结构堆（heap）双端队列（deque）红黑树（BST）
元素顺序按优先级出队先进先出（FIFO）按 key 排序
插入/删除复杂度O(log n)O(1)O(log n)
适用场景任务调度、最短路径普通队列去重、有序存储

总结

priority_queue 是 C++ STL 中的 优先队列，适用于 任务调度、最短路径和 Huffman 编码 等场景。默认是 大顶堆，可通过 greater<> 实现 小顶堆，也可以自定义排序规则。


http://www.ppmy.cn/devtools/166736.html

相关文章

c++介绍信号六

c++介绍信号六

信号量是c中实现对有限资源访问控制&#xff0c;现成通过信号量获得对资源访问的许可。可用资源大于0&#xff0c;线程可以对资源进行访问&#xff0c;此时计数器减1。当计数器为0时&#xff0c;不可访问资源&#xff0c;线程进入等待。当资源释放时&#xff0c;线程结束等待&a…
阅读更多...
Day24 洛谷真题讲解（递归方法找数）

Day24 洛谷真题讲解（递归方法找数）

我当时一看到这道题&#xff0c;第一想法就是如何能整k个循环&#xff0c;其实自己也知道这个几乎没法整&#xff0c; 然后我就感觉这道题很可以利用到那些复杂的方法 但是我真的没想太通 然后在一个很好的up主中我找到了一个讲的很好的 大家看下面的那个 大家重点看一下上…
阅读更多...
大白话如何使用 CSS 实现响应式布局？请列举一些常见的方法。

大白话如何使用 CSS 实现响应式布局？请列举一些常见的方法。

大白话如何使用 CSS 实现响应式布局&#xff1f;请列举一些常见的方法。 答题思路 首先要解释什么是响应式布局&#xff0c;让读者明白其概念和重要性。然后依次介绍常见的实现响应式布局的CSS方法&#xff0c;包括媒体查询、弹性布局&#xff08;Flexbox&#xff09;、网格布…
阅读更多...
【蓝桥杯每日一题】3.8

【蓝桥杯每日一题】3.8

&#x1f3dd;️专栏&#xff1a; 【蓝桥杯备篇】 &#x1f305;主页&#xff1a; f狐o狸x 抱一丝各位&#xff0c;前面两个月生了一场重病没有更新&#xff0c;懒病太严重了&#xff0c;从现在开始接着这个专题更新 每天刷一题&#xff0c;头发少一根&#xff1b;但若放弃治疗…
阅读更多...
数据量过大的时候导出数据很慢

数据量过大的时候导出数据很慢

原因解析 速度慢无非两个原因: sql取数很慢程序很慢 sql很慢有3种原因: sql本身查询不合理,需要优化数据库没有索引多次频繁访问数据,造成了不必要的开销 取消多次获取数据,一次获取 框定一个大致的范围,获取此次查询的所有数据使用map设置数据,没有主键使用傅和主键拼接数据 /…
阅读更多...
Java多线程与高并发专题——阻塞和非阻塞队列的并发安全原理是什么？

Java多线程与高并发专题——阻塞和非阻塞队列的并发安全原理是什么？

引入 之前我们探究了常见的阻塞队列的特点&#xff0c;在本文我们就以 ArrayBlockingQueue 为例&#xff0c;首先分析 BlockingQueue &#xff0c;也就是阻塞队列的线程安全原理&#xff0c;然后再看看它的兄弟——非阻塞队列的并发安全原理。 ArrayBlockingQueue 源码分析 …
阅读更多...
【网络协议详解】——QOS技术（学习笔记）

【网络协议详解】——QOS技术（学习笔记）

目录 QoS简介 QoS产生的背景 QoS服务模型 基于DiffServ模型的QoS组成 MQC简介 MQC三要素 MQC配置流程 优先级映射配置（DiffServ域模式） 优先级映射概述 优先级映射原理描述 优先级映射 PHB行为 流量监管、流量整形和接口限速简介 流量监管 流量整形 接口限速…
阅读更多...
什么样的场景适用redis？redis缓存是什么？

什么样的场景适用redis？redis缓存是什么？

基于 Java SSH 老项目、数据量大、查询慢、尽量少改动的现状&#xff0c;如果加入 Redis&#xff0c;可以从哪些场景切入&#xff1a; 1. 高频读取、低频更新的数据 场景示例&#xff1a; 商品信息、用户基础资料&#xff08;每日读取百万次&#xff0c;每周更新一次&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023