priority_queue 优先队列

读完能做什么

• 能用 priority_queue 把数据按“最要紧的先处理”一个一个取出来，说清 top() 和 pop() 各做什么。
• 能解释默认情况下为什么数值最大的元素在 top()，并能用 greater<int> 改成最小值优先。
• 能写一条自定义比较规则，表达“先比优先级，优先级相同再比编号”这样的两个条件。
• 能说出同一个比较规则为什么在 sort 和 priority_queue 里含义相反，以及为什么优先队列不能按下标访问、也不能遍历。

为什么需要它

排队的两端是“先来先处理”（队列）和“后来的先处理”（栈），但很多任务的规则是第三种：每次都先处理当前最要紧的那一个。

• 急诊分诊：不管谁先到，病情最重的先看。
• 任务调度：任务不断产生，每一步都要挑出当前优先级最高的来做。

用数组也能做，但每次都要从头扫一遍找最要紧的那个：

int a[1005], n = 0;
int best = 0;                        // 假设下标 0 是当前最要紧的
for (int i = 1; i < n; i++) {
    if (a[i] > a[best]) best = i;    // 找更大的
}
// 处理 a[best]，再把它从数组里删掉（后面的元素要整体前移）

这段片段（省略了头文件和 main）能说明问题：找一个最要紧的就要扫一遍，是 O(n)；把中间的元素删掉还要移动元素。如果“插入新数据”和“取出最要紧的数据”交替发生很多次，这样写会很慢。我们需要一个把这些工作都包好的工具，这就是 priority_queue。

它是什么

一句话：priority_queue 是每次取出当前优先级最高的元素的容器适配器。

直观模型是一个“不断调整的队伍”：元素进进出出，但无论中间怎么变，排在最上面的那一个永远是当前最要紧的。

容器适配器。 priority_queue 自己不管数据怎么存，它拿一个现成的容器（默认是 vector）当底座，再在底座上维护“堆”的结构，只把队顶操作包装出来。所以它叫适配器，和 queue 队列 是一类东西，只是排队的规则不同。

优先级的含义由比较规则决定。 不写规则时用的是 less<int>，它把“数值大”理解成“优先级高”，所以数值最大的元素在顶上。换成 greater<int>，“数值小”就变成“优先级高”，最小的元素在顶上。本页后面会详细讲这两条规则。

priority_queue 留下的是规则认为“最大”的那个元素。 规则 cmp(a, b) 的含义和 sort 里一样：cmp(a, b) == true 表示“按这条规则，a 应该排在 b 前面”。区别在两个容器对这份顺序的取用方式：sort 把它从左到右铺成序列，priority_queue 只把“排在最后”（规则认为最大）的那个元素放在 top() 上。所以同一个 less<int>，sort 得到升序，优先队列得到最大值优先。后面用同一条规则在两个容器上对比。

模板尖括号里的三个参数。 写成 priority_queue<int, vector<int>, greater<int>> 时：

只写 priority_queue<int> 时后两个参数自动取默认值，所以 priority_queue<int> 等价于 priority_queue<int, vector<int>, less<int>>。

堆（选读）。 底层用“堆”这种结构来维护顶部元素：插入和删除都只需要 O(log n) 的时间，不需要把元素真正排好序。堆的内部排列是实现的自由，不是接口保证——你可能在书上看到“堆就是一棵完全二叉树”，那只是理解方式；本页只依赖接口给出的行为。

使用时要 #include <queue>，本页示例用 #include <bits/stdc++.h> 一次包含全部标准头文件。

不能按下标访问，也不能遍历。 priority_queue 不提供 []，也没有 begin()、end()。要看队列里有什么，只能不断地 top() 再 pop()，一个一个取出来。

最小可运行示例

#include <bits/stdc++.h>
using namespace std;

int main() {
    priority_queue<int> pq;          // 默认：优先级高的（数值大的）先出

    pq.push(4);
    pq.push(1);
    pq.push(7);
    pq.push(3);
    cout << "插入 4 1 7 3 后，size = " << pq.size() << '\n';
    cout << "此时 top = " << pq.top() << '\n';

    cout << "依次取出：";
    while (!pq.empty()) {
        cout << pq.top() << ' ';     // 先看当前优先级最高的
        pq.pop();                    // 再把它删掉
    }
    cout << '\n';
    cout << "取完后 size = " << pq.size() << ", empty = " << pq.empty() << '\n';
    return 0;
}

输出：

插入 4 1 7 3 后，size = 4
此时 top = 7
依次取出：7 4 3 1 
取完后 size = 0, empty = 1

逐行看：

• priority_queue<int> pq; 创建一个空的优先队列，size() 是 0。
• 四次 push 把 4、1、7、3 依次放进去。注意放入的顺序是 4、1、7、3，与后面取出的顺序完全不同。
• pq.top() 返回当前优先级最高的元素，得到 7。它只是“看”，不删除元素，所以 size() 还是 4。
• while (!pq.empty()) 循环里先 top() 取值、再 pop() 删除，取出顺序是 7 4 3 1：从最要紧到最不要紧。
• 全部取完后 size() 变成 0，empty() 打印 1（bool 输出默认是 0/1）。

一步步看变化

沿 4、1、7、3 这组数据走一遍，每一步都看“顶部现在是谁”：

第 5 到第 8 步是输出里 7 4 3 1 的来历：每次 pop() 删掉当前的顶部，下一个最要紧的元素自动升上来。第 5 步也能看出 top() 只读——它返回 7 之后，size() 仍然是 4，真正删除元素的是 pop()。

这张表只展示了 top() 的值，“队列里有哪些元素”一列也只列出元素本身，不表示它们的摆放顺序：那是实现细节，接口不保证，也不允许通过下标或迭代器去看。你唯一能确定的是“顶部永远是当前最要紧的”。

逐项扩展核心操作

最小值优先：greater<int>

把第三模板参数换成 greater<int>，规则就变成“数值小的优先级高”：

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 第二个模板参数是底层容器，第三个是"比较规则"
    priority_queue<int, vector<int>, greater<int>> pq;

    pq.push(4);
    pq.push(1);
    pq.push(7);
    pq.push(3);
    cout << "此时 top = " << pq.top() << '\n';

    cout << "依次取出：";
    while (!pq.empty()) {
        cout << pq.top() << ' ';
        pq.pop();
    }
    cout << '\n';
    return 0;
}

输出：

此时 top = 1
依次取出：1 3 4 7 

数据还是 4、1、7、3，只是规则换了：top() 从 7 变成 1，取出顺序从 7 4 3 1 变成 1 3 4 7。以后想“每次处理最小的”，就写 greater<int>。

greater<int> 是标准库提供的函数对象，它的含义和写法在 比较规则与函数对象 里讲过：greater<int>()(a, b) 返回 a > b。

同一条规则在 sort 和 priority_queue 上的差别

这是最容易搞反的一点，用同一条规则在两个容器上各跑一次就清楚了：

#include <bits/stdc++.h>
using namespace std;

int main() {
    const vector<int> base = {4, 1, 7, 3};

    vector<int> a = base;
    sort(a.begin(), a.end(), less<int>());
    cout << "sort + less<int>()    ：";
    for (int x : a) cout << x << ' ';
    cout << '\n';

    vector<int> b = base;
    sort(b.begin(), b.end(), greater<int>());
    cout << "sort + greater<int>() ：";
    for (int x : b) cout << x << ' ';
    cout << '\n';

    priority_queue<int> pqLess;              // 默认就是 less<int>
    for (int x : base) pqLess.push(x);
    cout << "priority_queue 默认   ：";
    while (!pqLess.empty()) {
        cout << pqLess.top() << ' ';
        pqLess.pop();
    }
    cout << '\n';

    priority_queue<int, vector<int>, greater<int>> pqGreater;
    for (int x : base) pqGreater.push(x);
    cout << "priority_queue greater：";
    while (!pqGreater.empty()) {
        cout << pqGreater.top() << ' ';
        pqGreater.pop();
    }
    cout << '\n';
    return 0;
}

输出：

sort + less<int>()    ：1 3 4 7 
sort + greater<int>() ：7 4 3 1 
priority_queue 默认   ：7 4 3 1 
priority_queue greater：1 3 4 7 

四条输出分两组看，规则和结果的关系如下：

原因是两个容器用同一条规则时取的方向不同（规则本身的含义没变，cmp(a, b) == true 都表示 a 按规则排在 b 前面）：

• sort 按规则把元素从左到右铺成有序序列。用 less 时小的排在前面，所以是升序。
• priority_queue 把这条顺序里“最后面”（规则认为最大）的元素留在 top() 上先取出。用 less 时数值最大的元素留在顶上，所以最大的先出。

同一句“用 less”，在 sort 里得到升序，在优先队列里得到最大值优先——这就是必须记清楚的区别。

自定义规则：两个条件的优先级

任务往往不是只比一个数。下面这些任务按“优先级数字大的先做；优先级相同时，编号小的先做”处理：

规则用结构体 + operator() 写（写法见 比较规则与函数对象）：

#include <bits/stdc++.h>
using namespace std;

struct Task {
    int priority;    // 优先级，数字越大越要紧
    int id;          // 编号
};

struct TaskCmp {
    // 返回 true 表示 a 排在 b 的后面：b 的优先级更高
    bool operator()(const Task& a, const Task& b) const {
        if (a.priority != b.priority) return a.priority < b.priority;
        return a.id > b.id;
    }
};

int main() {
    priority_queue<Task, vector<Task>, TaskCmp> pq;

    pq.push({1, 1});     // 优先级 1，编号 1
    pq.push({3, 5});     // 优先级 3，编号 5
    pq.push({2, 2});     // 优先级 2，编号 2
    pq.push({3, 3});     // 优先级 3，编号 3

    cout << "处理顺序：" << '\n';
    while (!pq.empty()) {
        Task t = pq.top();
        pq.pop();
        cout << "优先级 " << t.priority << "，编号 " << t.id << '\n';
    }
    return 0;
}

输出：

处理顺序：
优先级 3，编号 3
优先级 3，编号 5
优先级 2，编号 2
优先级 1，编号 1

规则要反着读一遍才不容易写错：cmp(a, b) == true 表示 a 排在 b 后面，所以

• a.priority < b.priority → a 的优先级更低 → a 排后面，优先级大的留在顶部；
• 优先级相同时 a.id > b.id → a 的编号更大 → a 排后面，编号小的留在顶部。

如果第二条 return 写成 a.id < b.id，同优先级的编号顺序就会反过来。这也说明：规则里没有比较的信息，不会替你排序——想让“同优先级按编号”生效，就必须把编号写进规则。

不能按下标访问，也不能遍历

// 错误示例：priority_queue 没有 []、也没有迭代器，下面两句都不能通过编译
#include <bits/stdc++.h>
using namespace std;

int main() {
    priority_queue<int> pq;
    pq.push(1);

    cout << pq[0] << '\n';                           // 没有 operator[]
    for (auto it = pq.begin(); it != pq.end(); ++it) {   // 没有 begin()/end()
        cout << *it << '\n';
    }
    return 0;
}

这段不能通过编译：编译器的报错分别是 no match for 'operator[]' 和 'class std::priority_queue<int>' has no member named 'begin'。这不是缺陷，而是优先队列的规则允许：元素按优先级进进出出，如果还能用下标直接跳到中间，就不能保证这个规则了。想看全部内容时，只能像前面的例子那样不断 top() 再 pop()。

复杂度：取顶是常数，进出是对数

n 是队列里当前的元素个数。对比一下“用数组每次扫一遍找最大”的 O(n)：数据多、操作频繁时，优先队列快得多。

什么时候选它、哪里容易错

top() 只读，pop() 才删除。 要“取出并处理”最要紧的元素，标准写法是两步：先 t = pq.top() 记住它，再 pq.pop() 删掉它。pop() 不返回被删掉的元素，写成 Task t = pq.pop(); 会编译失败。

空队列不能取顶，也不能弹出。 top() 和 pop() 都要求队列非空。空队列上调用属于未定义行为，可能读到垃圾值，也可能崩溃，不能靠“它应该会给我 0”来猜。用之前先判断 pq.empty()。

不能按下标访问，不能遍历。 没有 pq[0]，没有 begin()/end()。需要看全部内容时只能逐个 top() + pop()，或者把元素另外存一份。

内部排列不是接口保证。 只有 top() 是“当前最要紧的那个”这一点有保证；底层数组里哪个元素排在第几个位置是实现细节。不要写依赖“堆里元素的摆放顺序”的程序，也不要因为书上说的堆是某种树就以为能这样访问数据。

规则方向别写反。 在 priority_queue 里，cmp(a, b) == true 表示 a 排到后面。写自定义规则前先按这句话检查一遍：想要谁留在顶部，就让它跟别人比较时“永远不返回 true”。

需要“全部按顺序输出”时，优先队列不一定划算。 把 n 个元素全取出来是 O(n log n)，和直接 sort 一样，但代码更长。优先队列的用处是“边插入边取最要紧的”，比如数据一边生成一边处理。

选读：底层容器可以换。 第二个模板参数默认是 vector，也可以写 priority_queue<int, deque<int>>。它只要求底层容器支持随机访问和在尾部的增删，日常用默认的 vector 就够了。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），请先手推出输出，再运行核对：

priority_queue<int> pq;
pq.push(4);
pq.push(1);
pq.push(7);
pq.push(3);
pq.push(5);          // 中途插入一个新值

while (!pq.empty()) {
    cout << pq.top() << ' ';
    pq.pop();
}
cout << '\n';

第 2 题：修改代码

把最小可运行示例里的程序（数据是 4、1、7、3）改成“最小值先处理”：题目要求输出 1 3 4 7。

验证条件：先说出改动之后 top() 是哪个元素，再运行核对。

#include <bits/stdc++.h>
using namespace std;

int main() {
    priority_queue<int> pq;

    pq.push(4);
    pq.push(1);
    pq.push(7);
    pq.push(3);
    pq.push(5);          // 中途插入一个新值

    cout << "依次取出：";
    while (!pq.empty()) {
        cout << pq.top() << ' ';
        pq.pop();
    }
    cout << '\n';
    return 0;
}

依次取出：7 5 4 3 1 

#include <bits/stdc++.h>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> pq;   // 最小值优先

    for (int x : {4, 1, 7, 3}) pq.push(x);

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

1 3 4 7 

立即练习

两道题都只需要数组、循环和本页的优先队列操作。做完后请说明：如果换成默认的“最大值优先”，合并果子的答案会变大还是变小？为什么？