C / C++ / 系统课时

priority_queue 怎样按优先级取值

priority_queue 怎样按优先级取值

std::priority_queue 不是按进入先后取元素,而是始终让“优先级最高”的元素位于 top()。默认比较规则会把较大的值放到顶部,因此常被称为最大堆行为。本节用带优先级的任务说明插入、查看顶部与删除顶部的完整过程。

学习目标

  • 理解 priority_queue 默认让较大元素位于 top() 的规则
  • 使用 push、top、pop 按优先级处理任务
  • 知道相同优先级和最小优先队列需要额外比较规则

top 表示当前最高优先级

普通 queue 的队首由进入时间决定,而 priority_queue 的 top() 由比较结果决定。默认使用 std::less,对常见数值类型表现为较大值优先;每次插入或删除后,容器会重新维护顶部元素,但不会承诺其余元素形成完整的全局排序。

priority_queue 顶部元素与最大堆关系

把“优先级数字”和“任务名称”放进 std::pair<int, std::string> 时,默认比较会先比较 first。因此只要优先级数字不同,数字较大的任务就会先出现在 top()。

按优先级处理任务

下面加入三个任务,优先级分别为 2、5、1。循环每次读取 top(),处理后调用 pop() 删除当前最高优先级任务。

cpp
#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;
}

预期输出:

text
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 更直接。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

priority_queue 怎样按优先级取值

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通