C / C++ / 系统课时
怎样构造一个最小优先队列
怎样构造一个最小优先队列
std::priority_queue 默认把最大元素放在队首。如果业务需要每次优先取最小值,可以使用 std::greater 改变排序方向;元素是自定义类型时,则通过比较器明确“谁的优先级更高”。
学习目标
- 使用
std::greater构造最小优先队列 - 为自定义类型编写符合要求的比较器
- 理解比较器方向与
top()返回元素之间的关系
默认行为为什么是最大值优先
std::priority_queue<T> 默认使用 std::less<T> 比较元素,因此 top() 返回当前优先级最高的元素;对于普通数字,这通常就是最大值。
如果希望最小值优先,需要同时指定元素类型、底层容器和比较器:
std::priority_queue<int, std::vector<int>, std::greater<int>>
这里的 std::vector<int> 是底层存储容器,std::greater<int> 改变了优先关系,使最小元素出现在 top()。
使用 greater 构造最小优先队列
下面的程序依次压入四个整数,再不断读取和删除队首元素。
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::priority_queue<int, std::vector<int>, std::greater<int>> minQueue;
minQueue.push(8);
minQueue.push(3);
minQueue.push(10);
minQueue.push(1);
while (!minQueue.empty()) {
std::cout << minQueue.top() << ' ';
minQueue.pop();
}
std::cout << '\n';
return 0;
}预期输出
1 3 8 10push() 并不是把数据整体排成一个有序数组,而是维护堆结构。因此应通过 top() 获取当前最小值,通过 pop() 删除它,而不要假设底层元素已经按升序连续排列。
自定义类型需要自定义比较器
当元素没有直接符合业务含义的大小关系时,可以定义比较器。例如任务调度中规定数字越小优先级越高,并在优先级相同时让编号较小的任务先执行。
#include <iostream>
#include <queue>
#include <string>
#include <vector>
struct Task {
int priority;
int id;
std::string name;
};
struct TaskCompare {
bool operator()(const Task& a, const Task& b) const {
// 返回 true 表示 a 的优先级应排在 b 后面。
if (a.priority != b.priority) {
return a.priority > b.priority;
}
return a.id > b.id;
}
};
int main() {
std::priority_queue<Task, std::vector<Task>, TaskCompare> tasks;
tasks.push({2, 10, "backup"});
tasks.push({1, 20, "alert"});
tasks.push({1, 5, "health-check"});
while (!tasks.empty()) {
const Task& task = tasks.top();
std::cout << task.priority << ' ' << task.id << ' ' << task.name << '\n';
tasks.pop();
}
return 0;
}预期输出
1 5 health-check
1 20 alert
2 10 backup比较器最容易写反的地方
priority_queue 的比较器不能简单理解成“返回 true 的元素排在前面”。更实用的判断方式是:比较器返回 true,表示左侧元素的优先级低于右侧元素。
因此,想让较小的 priority 先出队时,比较器应写成 a.priority > b.priority。如果误写成 <,效果会变成数值较大的任务优先。
对于普通数字,优先使用 std::greater<T>,代码最简洁;只有排序规则包含多个字段或业务语义时,再编写自定义比较器。