C / C++ / 系统课时
priority_queue 怎样按优先级取值
priority_queue 怎样按优先级取值
std::priority_queue 不是按进入先后取元素,而是始终让“优先级最高”的元素位于 top()。默认比较规则会把较大的值放到顶部,因此常被称为最大堆行为。本节用带优先级的任务说明插入、查看顶部与删除顶部的完整过程。
学习目标
- 理解
priority_queue默认让较大元素位于top()的规则 - 使用
push、top、pop按优先级处理任务 - 知道相同优先级和最小优先队列需要额外比较规则
top 表示当前最高优先级
普通 queue 的队首由进入时间决定,而 priority_queue 的 top() 由比较结果决定。默认使用 std::less,对常见数值类型表现为较大值优先;每次插入或删除后,容器会重新维护顶部元素,但不会承诺其余元素形成完整的全局排序。

把“优先级数字”和“任务名称”放进 std::pair<int, std::string> 时,默认比较会先比较 first。因此只要优先级数字不同,数字较大的任务就会先出现在 top()。
按优先级处理任务
下面加入三个任务,优先级分别为 2、5、1。循环每次读取 top(),处理后调用 pop() 删除当前最高优先级任务。
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
int main() {
using Task = std::pair<int, std::string>;
std::priority_queue<Task> tasks;
tasks.push({2, "write report"});
tasks.push({5, "fix outage"});
tasks.push({1, "backup"});
while (!tasks.empty()) {
const Task current = tasks.top();
std::cout << "priority=" << current.first
<< ", task=" << current.second << '\n';
tasks.pop();
}
return 0;
}预期输出:
priority=5, task=fix outage
priority=2, task=write report
priority=1, task=backup这里的出队顺序与插入顺序无关。fix outage 虽然第二个加入,但优先级 5 最大,所以第一次 top() 就得到它。
默认最大堆意味着什么
priority_queue<T> 默认使用 std::vector<T> 保存元素,并通过 std::less<T> 确定优先关系。对整数来说,top() 就是当前最大值;对 std::pair 来说,会先比较 first,若 first 相同,再比较 second。
与 queue 一样,pop() 不返回被删除的元素。需要使用顶部值时,先读取 top(),再调用 pop();访问前仍应先检查 empty()。
相同优先级与最小优先队列
本例使用 pair<int, string>,所以当两个任务的优先级数字相同时,任务名称也会参与比较。这通常不是业务想要的“同优先级保持先来先处理”。如果需要稳定的先后规则,可以把递增序号一并存入任务对象,并提供自定义比较器。
如果目标是让最小值优先,可以把比较器改成 std::greater<int>,同时把底层容器显式写为 std::vector<int>。无论比较规则怎样变化,使用方式都不变:top() 查看当前最高优先元素,pop() 删除它。
当“最紧急、分数最高、代价最小”等比较规则决定处理顺序时,priority_queue 很合适;如果只要求严格的先到先服务,则普通 queue 更直接。