C++ priority_queue（优先队列）

在日常生活中，并不是所有排队都只看 “先来后到”。比如医院急诊室会优先救治危重病人，操作系统也会优先执行紧急程度更高的任务。在这类场景下，决定处理顺序的不是谁先来，而是 “谁的优先级更高”。

在 C++ 中，std::priority_queue（优先队列）就是专门用来解决这类需求的容器适配器。和普通队列 std::queue 不同，不管元素按什么先后顺序放进优先队列，每次排在最上面、最先被取出来的，总是当前优先级最高的那个元素，默认也就是数值最大的元素。

priority_queue 的定义与常用操作

std::priority_queue 底层默认使用 std::vector 保存数据，并在内部自动维护一种叫做 “堆（Heap）” 的数据结构。每次放入新元素或移除顶部元素后，它都会自动调整内部顺序，保证当前优先级最高的元素始终浮在最顶部。

这里有一个初学者特别容易写错的细节：使用 std::priority_queue 时，引入的依然是 <queue> 头文件，C++ 标准库里并没有名为 <priority_queue> 的头文件。

语法：

#include <queue>

std::priority_queue<元素类型> 变量名;

说明：

尖括号 <> 里指定保存的元素类型即可，比如 std::priority_queue<int> pq; 就定义了一个存放整数的空优先队列。与其他容器适配器一样，平时我们通过 push() 把元素一个个放进去，需要清空时直接写 pq = {}; 即可。常用的成员函数如下表所示。

priority_queue 的基本操作

默认情况下，std::priority_queue 认为 “数值越大，优先级越高”，在数据结构中也常被称为 “大顶堆” 或 “最大堆”。每次调用 push() 放入新元素后，容器都会自动调整内部位置，让当前最大的元素始终处在 top() 顶部位置。

示例 1：按最大值优先出队

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    pq.push(30);                         // 乱序放入 4 个整数
    pq.push(10);
    pq.push(50);
    pq.push(20);

    std::cout << "当前最大值：" << pq.top() << '\n';
    std::cout << "元素总个数：" << pq.size() << '\n';

    while (!pq.empty()) {
        std::cout << pq.top() << ' ';    // 取出当前最大元素
        pq.pop();                        // 移除当前顶部元素
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

当前最大值：50
元素总个数：4
50 30 20 10

分析：

在这个例子中，虽然我们是按照 30、10、50、20 的先后顺序调用 push() 的，但 priority_queue 会自动把最大的 50 调整到最顶部，因此 pq.top() 首先看到的是 50。随后在 while 循环中，每次移除顶部元素后，剩余元素里的最大值都会自动补上来，最终打印出从大到小的 50 30 20 10。

在实际开发中，队列里存放的通常不只是一个单独的数字，而是 “优先级 + 任务内容” 的组合。这时我们可以直接配合前面学过的 std::pair，把表示优先级的数字放在 first，把具体任务名称放在 second。请看下面例子。

示例 2：按紧急程度处理任务

#include <iostream>
#include <queue>
#include <string>
#include <utility>

int main() {
    std::priority_queue<std::pair<int, std::string>> tasks;

    tasks.push({2, "整理测试报告"});
    tasks.push({5, "修复登录故障"});
    tasks.push({1, "清理临时文件"});

    while (!tasks.empty()) {
        auto task = tasks.top();    // 取出顶部任务
        tasks.pop();                // 移出优先队列
        std::cout << task.first << ": " << task.second << '\n';
    }
    return 0;
}

运行结果如下。

5: 修复登录故障
2: 整理测试报告
1: 清理临时文件

分析：

两个 std::pair 比较大小时会优先比较第 1 个成员 first。因此把优先级和任务名称打包放入优先队列后，first 数值最大的 {5, "修复登录故障"} 会自动浮到顶部最先处理。如果两个任务的优先级数值相同，则会接着按 second 的字典序决定先后。

这里小伙伴们要注意，表示优先级的数字一定要放在 pair 的第 1 个成员位置。如果反过来写成 std::pair<std::string, int> 把任务名称放在前面，优先队列就会变成按任务名称的字母顺序排队，而不是按紧急程度排队了。

改为最小值优先出队

有时我们的优先级规则恰好反过来：数字越小，代表优先级越高，比如比赛第 1 名优先于第 2 名，或者预计耗时最短的任务优先执行。这时如果希望每次从 top() 取出最小的元素（即 “小顶堆”），我们需要把类模板的 3 个参数写完整。

语法：

#include <functional>
#include <queue>
#include <vector>

std::priority_queue<类型, std::vector<类型>, std::greater<类型>> 变量名;

说明：

初次看到这么长的尖括号不用着急，以存放整数 int 为例，我们把里面的 3 个模板参数拆开看就很清楚了：

• 第 1 个参数（元素类型）：队列里实际保存的数据类型，比如 int。
• 第 2 个参数（底层容器）：优先队列内部用来存数据的容器，固定写默认的 std::vector<int> 即可。因为要指定后面的第 3 个参数，中间的第 2 个参数不能省略。
• 第 3 个参数（比较规则）：传入 <functional> 头文件中的 std::greater<int>，表示让数值更小的元素浮到最顶部。

可能有些小伙伴会觉得奇怪：“前面在 std::set 里填入 std::greater 是从大到小排，为什么在优先队列里填入 std::greater 反而变成了最小值优先呢？”

这是因为优先队列里的比较规则用来决定 “谁的优先级更低、应该往下沉”。默认规则 std::less 让数值小的往下沉，所以最大的数浮在最上面。改成 std::greater 之后，就变成了让数值大的往下沉，自然就是最小的数浮在 top() 顶部了。

大家平时写代码不需要每次都去绕一遍底层过程，只需要记住一句话就可以了：默认是大数优先（大顶堆），填 std::greater 就是小数优先（小顶堆）。

示例 3：改为最小值优先出队

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minPq;

    minPq.push(30);
    minPq.push(10);
    minPq.push(50);
    minPq.push(20);

    std::cout << "当前最小值：" << minPq.top() << '\n';

    while (!minPq.empty()) {
        std::cout << minPq.top() << ' ';
        minPq.pop();
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

当前最小值：10
10 20 30 50

分析：

把示例 3 和前面的示例 1 对比起来看，放入的同样是 30、10、50、20 这 4 个整数。但因为定义 minPq 时指定了 std::greater<int>，此时最小的 10 排在了最顶部，依次弹出全部元素时的顺序也变成了从小到大的 10 20 30 50。

三种容器适配器的对比

std::stack、std::queue 和 std::priority_queue 同属于 STL 中的容器适配器。它们都不支持下标 [] 访问，也不支持范围 for 循环遍历，专门用来表达特定的数据进出规则。它们之间的主要区别如下表所示。

在实际开发中，小伙伴们只要记住它们各自的出队规则，就能快速选出合适的工具。最后放进去的元素要先处理，选择 std::stack。先放进去的元素要先处理，选择 std::queue。不管谁先来，总是挑当前最大或最小的元素先处理，就选择 std::priority_queue。