当前位置：首页 > news >正文

priority_queue（堆）干货归纳+用法示例

news 2025/7/14 8:47:29

10.priority_queue

一.priority_queue（堆Heap）简介
- 1.堆的特点：
- 2.使用场景：
二.成员函数
- 1.构造函数：priority_queue构造函数方式：
- 2.push()函数：向priority_queue中插入一个元素：
- 3.pop()函数：弹出priority_queue中的队首元素：
- 4.top()函数：获取priority_queue中的队首元素：
- 5.size()函数：获取priority_queue中的元素个数：
- 6.empty()函数：判断priority_queue是否为空：
三.程序示例

一.priority_queue（堆Heap）简介

在C++中，堆（Heap）是一种特殊的树状数据结构，其中每个节点都比其子节点大或小（具体取决于堆的类型）。堆通常用于实现优先队列和排序算法。

1.堆的特点：

完全二叉树：堆是一种完全二叉树，即除了最后一层节点可以不满外，其它层节点都必须满足。
有序性：堆中的每个节点都比其子节点大或小（具体取决于堆的类型），满足堆的有序性。
快速插入和删除：由于堆的特殊结构，可以在O(log n)的时间复杂度内进行插入和删除操作。

C++中有两种类型的堆：最大堆（Max Heap）和最小堆（Min Heap）。最大堆的每个节点都比其子节点大，而最小堆的每个节点都比其子节点小。通常使用头文件中的priority_queue类来实现堆。

priority_queue类特点：

自动排序：priority_queue会自动按照元素的大小进行排序，因此每次取出的元素都是当前最大（或最小）的元素。
高效的插入和删除操作：priority_queue使用堆的数据结构，插入和删除元素的时间复杂度为O(log
n)，其中n是容器中的元素数量。
支持随机访问：虽然priority_queue本身不支持随机访问，但是可以通过其底层的容器（默认是vector）来实现随机访问。

2.使用场景：

找到数组或序列中的第K大或第K小元素；
求一组数据的中位数；
排序算法，如堆排序、选择排序等；
优先队列，如Dijkstra算法、Prim算法等。

priority_queue的使用场景：

求Top K元素：如果需要求一个序列中最大（或最小）的K个元素，可以使用priority_queue。
任务调度：如果有多个任务需要按照优先级进行执行，可以将任务按照优先级放入priority_queue中，每次从队列中取出优先级最高的任务进行执行。
Dijkstra算法：Dijkstra算法是求解单源最短路径的经典算法之一，其中需要使用priority_queue来维护当前距离起点最短的点

。

二.成员函数

1.构造函数：priority_queue构造函数方式：

默认构造函数：创建一个空的priority_queue（默认使用std::less函数对象来进行排序，也就是说它是一个大根堆，将最大值放在队首）。

priority_queue<int> q;  // 创建一个空的priority_queue

带参构造函数：创建一个priority_queue，并将参数中的元素放入其中。

priority_queue<int> q({1, 2, 3, 4});  // 创建一个priority_queue，并将元素1、2、3、4放入其中

自定义比较函数的构造函数：可以通过自定义比较函数来指定priority_queue的排序方式。

auto cmp = [](int a, int b) { return a > b; };
priority_queue<int, vector<int>, decltype(cmp)> q(cmp);  // 创建一个priority_queue，使用自定义的比较函数

2.push()函数：向priority_queue中插入一个元素：

q.push(10);  // 向priority_queue中插入元素10

3.pop()函数：弹出priority_queue中的队首元素：

q.pop();  // 弹出priority_queue中的队首元素

4.top()函数：获取priority_queue中的队首元素：

int x = q.top();  // 获取priority_queue中的队首元素

5.size()函数：获取priority_queue中的元素个数：

int s = q.size();  // 获取priority_queue中的元素个数

6.empty()函数：判断priority_queue是否为空：

bool is_empty = q.empty();  // 判断priority_queue是否为空

三.程序示例

下是一个使用最大堆求一组数据的前K大元素的例子：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;vector<int> topk(vector<int>& nums, int k) {priority_queue<int, vector<int>, less<int>> pq; // 最大堆for (int num : nums) {pq.push(num);}vector<int> result;while (!pq.empty() && result.size() <k ) {result.push_back(pq.top());pq.pop();}return result;
}int main() {vector<int> nums = { 3, 2, 10, 5, 6, 4,3,7 };int k = 2;vector<int> result = topk(nums, k);for (int num : result) {cout << num << " ";}return 0;
}

在这里插入图片描述

该程序使用最大堆求一组数据的前K大元素，将数据依次插入堆中，如果堆的大小小于K，则直接插入；否则，将堆顶元素与当前元素比较，如果堆顶元素比当前元素小，则弹出堆顶元素并插入当前元素。最后，将堆中所有元素依次取出并返回即可。