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

priority_queue的使用方法

news 来源：原创 2024/9/20 23:48:42

priority_queue 是 C++ 标准库中的一种容器适配器，用于实现优先队列（Priority Queue）。优先队列是一种特殊的队列，其中元素按照优先级顺序被访问。默认情况下，priority_queue 是一个最大堆，即优先级最高的元素（数值最大的元素）会首先被访问。

1. 基本用法

#include <iostream>
#include <queue>
#include <vector>using namespace std;int main() {// 创建一个 priority_queue，默认情况下是最大堆priority_queue<int> pq;// 插入元素pq.push(10);pq.push(30);pq.push(20);pq.push(5);// 输出并移除堆顶元素while (!pq.empty()) {cout << pq.top() << " ";  // 输出堆顶元素pq.pop();  // 移除堆顶元素}return 0;
}

运行结果

30 20 10 5

2. priority_queue 的关键操作

插入元素：push(value)

将元素插入到优先队列中，自动按照优先级进行排序。

访问堆顶元素：top()

返回优先队列中优先级最高的元素（对于最大堆，就是最大元素），但不移除它。

移除堆顶元素：pop()

移除优先队列中优先级最高的元素（最大元素）。

检查队列是否为空：empty()

如果优先队列为空，返回 true，否则返回 false。

获取队列大小：size()

返回优先队列中元素的数量。

3. 自定义比较函数

默认情况下，priority_queue 是一个最大堆（即大元素有更高的优先级），但有时候我们需要最小堆（即小元素有更高的优先级）或者自定义优先级顺序。这可以通过自定义比较函数或仿函数来实现。

最小堆的实现

#include <iostream>
#include <queue>
#include <vector>using namespace std;int main() {// 创建一个最小堆的 priority_queuepriority_queue<int, vector<int>, greater<int>> pq;// 插入元素pq.push(10);pq.push(30);pq.push(20);pq.push(5);// 输出并移除堆顶元素while (!pq.empty()) {cout << pq.top() << " ";  // 输出堆顶元素pq.pop();  // 移除堆顶元素}return 0;
}

自定义排序
有时我们希望对非基本类型的对象使用 priority_queue，并根据自定义规则排序。例如，我们有一个 pair<int, string>，并且希望根据 pair 的第一个元素（整数）进行最小堆排序。

#include <iostream>
#include <queue>
#include <vector>
#include <string>using namespace std;// 自定义比较函数
struct compare {bool operator()(const pair<int, string>& a, const pair<int, string>& b) {return a.first > b.first;  // 按照第一个元素（整数）升序排序（最小堆）}
};int main() {// 创建一个 priority_queue，按自定义比较函数排序priority_queue<pair<int, string>, vector<pair<int, string>>, compare> pq;// 插入元素pq.push({2, "two"});pq.push({1, "one"});pq.push({3, "three"});// 输出并移除堆顶元素while (!pq.empty()) {cout << pq.top().first << " " << pq.top().second << endl;pq.pop();}return 0;
}

运行结果

1 one
2 two
3 three

总结

priority_queue 是一种适配器容器，提供了按优先级顺序访问元素的功能。
默认情况下，它实现的是最大堆。
可以通过自定义比较函数或仿函数来实现最小堆或其他优先级排序。
常用的操作包括 push() 插入元素、top() 访问堆顶元素、pop() 移除堆顶元素等。

4. 当自定义函数返回排序解释

在 C++ 的 priority_queue 中，比较函数 operator() 返回 true 时的含义是：

priority_queue 是一个最大堆：默认情况下，它会将优先级最高的元素放在堆顶。
自定义比较函数的返回值：如果比较函数 operator() 返回 true，priority_queue 将认为第一个元素的优先级低于第二个元素。因此，第一个元素将排在第二个元素之后。

关键点

priority_queue 的默认行为：最大堆（即最大元素有最高优先级）。
比较函数的作用：比较函数的返回值 true 告诉 priority_queue，在堆中，第一个元素的优先级应该低于第二个元素。

如何判断是大顶堆还是小顶堆？
1. 大顶堆（最大堆）：

如果你希望 priority_queue 是一个大顶堆（最大堆），你希望大的元素优先级高，因此需要比较函数在第一个元素比第二个元素小时返回 true。
比较函数：return a < b; （或 a.first < b.first 对于 pair）。

2. 小顶堆（最小堆）：

如果你希望 priority_queue 是一个小顶堆（最小堆），你希望小的元素优先级高，因此需要比较函数在第一个元素比第二个元素大时返回 true。
比较函数：return a > b; （或 a.first > b.first 对于 pair）。

示例

大顶堆（默认行为）

struct customCompare {bool operator()(const int& a, const int& b) {return a < b;  // 返回 true 表示 a 优先级低于 b，所以 a 放在 b 之后}
};priority_queue<int, vector<int>, customCompare> pq;

在这个实现中：
当 a < b 返回 true 时，priority_queue 会认为 a 的优先级低于 b，所以 b 会被放在堆顶。这样实现的就是一个大顶堆。

小顶堆

struct customCompare {bool operator()(const int& a, const int& b) {return a > b;  // 返回 true 表示 a 优先级低于 b，所以 a 放在 b 之后}
};priority_queue<int, vector<int>, customCompare> pq;

在这个实现中：
当 a > b 返回 true 时，priority_queue 会认为 a 的优先级低于 b，所以 b 会被放在堆顶。这样实现的就是一个小顶堆。

5. 总结

返回 true 的含义：在 priority_queue 中，当比较函数 operator() 返回 true 时，它表示第一个元素的优先级低于第二个元素，因此第一个元素会排在第二个元素之后。
大顶堆（最大堆）：如果比较函数是 a < b，较大的元素会有更高的优先级，从而实现大顶堆。
小顶堆（最小堆）：如果比较函数是 a > b，较小的元素会有更高的优先级，从而实现小顶堆。