优先队列——谁最紧急谁先走

医院的急诊室有一个排队系统：哪个人病情最紧急，就最先被医生叫到。这就是“优先队列”的比喻——它根据你设定的“紧急程度”（比如数字大小），让优先级最高的元素最先离开，而不是按进来的顺序。

在C++中，priority_queue 默认是一个“最大堆”，也就是数值最大的元素最先出队。你可以想象成一个大堆，顶上永远是最重要的物品。当然，我们也可以改成最小堆，让最小的先出队。

优先队列有三个主要操作：push（加入一个元素）、pop（移除队首元素）、top（查看队首元素）。它的内部实现通常是一棵“堆”树，插入和删除的时间复杂度都是O(log n)，非常快。

一、用生活场景理解优先队列

场景1：急诊室分诊
病人按病情严重程度排队：危重病人插队到最前面，普通感冒只能往后排。护士每次叫号，都会叫当前最严重的病人。这就是一个“最大优先队列”——优先级（病情等级）最高的先出。

场景2：作业批改
老师要批改作业，但有一个规则：明天要交的作业（截止日期最近）先批改。如果每份作业都标记一个“紧急分数”（比如截止日期越近分数越大），那么老师每次从桌上选分数最高的作业来批。这就是优先队列的典型应用。

场景3：游戏中的技能冷却
游戏里有一个技能槽，你同时有多个技能可以放，但每个技能有不同的冷却时间。你想每次释放当前“冷却完成最早”的技能。这可以用最小堆实现：冷却时间越小的技能，优先级越高，越先被使用。

二、C++ 中的 priority_queue 详解

1. 创建优先队列

#include <iostream>
#include <queue>   // 优先队列的头文件
#include <vector>
using namespace std;

int main() {
    // 默认最大堆：数值最大的优先
    priority_queue<int> pq; // 最大堆，元素类型是int

    // 最小堆：数值最小的优先（需要指定三个模板参数）
    priority_queue<int, vector<int>, greater<int>> min_pq; // 最小堆
    return 0;
}

模板参数解释：
priority_queue<类型, 底层容器, 比较器>

第一个参数：元素类型（如 int）
第二个参数：底层容器，默认 vector<类型>，一般不改
第三个参数：比较器，less<类型> 是最大堆（默认），greater<类型> 是最小堆

小窍门：less 表示“小的优先级低”，所以大的在上面；greater 表示“大的优先级低”，所以小的在上面。

2. 常用操作

操作	代码	说明
添加元素	`pq.push(值);`	将元素加入队列，会自动调整堆
查看队首	`pq.top();`	返回优先级最高的元素（不删除）
删除队首	`pq.pop();`	移除优先级最高的元素
判空	`pq.empty();`	队列为空返回 `true`
大小	`pq.size();`	返回元素个数

注意： 没有 front() 或 back()，只有 top()。

3. 完整嵌套例子：数字排序

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    priority_queue<int> max_heap; // 最大堆
    max_heap.push(5);  // 数字5入队
    max_heap.push(1);
    max_heap.push(10);
    max_heap.push(3);

    cout << "最大堆出队顺序：";
    while (!max_heap.empty()) {
        cout << max_heap.top() << " "; // 依次输出 10 5 3 1
        max_heap.pop();
    }
    cout << endl;

    // 最小堆
    priority_queue<int, vector<int>, greater<int>> min_heap; // 最小堆
    min_heap.push(5);
    min_heap.push(1);
    min_heap.push(10);
    min_heap.push(3);
    cout << "最小堆出队顺序：";
    while (!min_heap.empty()) {
        cout << min_heap.top() << " "; // 依次输出 1 3 5 10
        min_heap.pop();
    }
    return 0;
}

运行结果：

最大堆出队顺序：10 5 3 1
最小堆出队顺序：1 3 5 10

三、自定义优先级：重载小于号

如果元素不是简单数字（比如结构体），我们需要告诉优先队列如何比较。两种方法：

方法1：在结构体内重载 < 运算符（最大堆需要 a < b 表示 a 优先级小于 b）

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct Patient {
    string name; // 病人姓名
    int level;   // 病情等级，越大越紧急

    // 重载小于号：用于最大堆
    bool operator < (const Patient & other) const {
        return this->level < other.level; // level越大越优先
    }
};

int main() {
    priority_queue<Patient> waiting_room; // 最大堆，按level降序

    waiting_room.push({"张三", 3});
    waiting_room.push({"李四", 5});
    waiting_room.push({"王五", 1});

    while (!waiting_room.empty()) {
        Patient cur = waiting_room.top();
        cout << cur.name << " 级别=" << cur.level << endl;
        waiting_room.pop();
    }
    return 0;
}

输出：

李四 级别=5
张三 级别=3
王五 级别=1

方法2：使用仿函数（函数对象） 作为比较器，适合自定义排序规则。

struct CompareByLevel {
    // 返回 true 表示 a 优先级低于 b（用于最大堆，即 level小的优先级低）
    bool operator()(const Patient & a, const Patient & b) {
        return a.level < b.level; // 和重载<一样，level大的优先
    }
};

int main() {
    // 使用仿函数
    priority_queue<Patient, vector<Patient>, CompareByLevel> pq;
    // ... 同上
}

四、新手常见的错误

❌ 错误1：对空队列使用 `top()` 或 `pop()`

priority_queue<int> pq;
cout << pq.top(); // 错误！队列为空，未定义行为（可能崩溃）

解决方法： 先检查 !pq.empty()。

❌ 错误2：忘记包含头文件 `<queue>`

#include <iostream>
using namespace std;
priority_queue<int> pq;  // 编译错误：priority_queue 未定义

解决方法： 加上 #include <queue>。

❌ 错误3：自定义类型忘记重载 `<` 或提供比较器

struct Student {
    string name;
    int score;
};
priority_queue<Student> pq;  // 编译错误：不知道如何比较 Student

解决方法： 要么重载 <，要么用仿函数。

❌ 错误4：以为 `priority_queue` 可以随机访问

cout << pq[0]; // 错误！priority_queue 不提供下标操作

解决方法： 只能用 top() 访问队首。

❌ 错误5：忽略 `pop()` 不会返回元素

很多新手写 int x = pq.pop(); 但 pop() 是 void。应该先 top() 再 pop()。

五、综合示例：合并有序链表（LeetCode 23）

这是一个经典面试题：给你 k 个有序链表，合并成一个有序链表。用优先队列可以高效实现：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 链表节点定义
struct ListNode {
    int val;          // 节点值
    ListNode *next;   // 指向下一个节点
    ListNode(int x) : val(x), next(nullptr) {}
};

// 比较器：最小堆，值小的优先出队
struct CompareNode {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val; // 注意：最小堆需要返回 a > b
    }
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    // 最小堆，里面存的是链表节点指针
    priority_queue<ListNode*, vector<ListNode*>, CompareNode> min_heap;

    // 把所有链表的头节点加入堆
    for (ListNode* head : lists) {
        if (head != nullptr) {
            min_heap.push(head);
        }
    }

    ListNode dummy(0);      // 哑节点，方便构建结果链表
    ListNode* tail = &dummy; // 尾指针

    while (!min_heap.empty()) {
        ListNode* cur = min_heap.top(); // 当前最小的节点
        min_heap.pop();

        tail->next = cur;   // 接到结果链表尾部
        tail = tail->next;

        if (cur->next != nullptr) {
            min_heap.push(cur->next); // 将下一个节点入堆
        }
    }
    return dummy.next;
}

思路： 每次从 k 个链表中取出最小的一个节点，然后把这个节点的下一个节点加入堆，重复直到堆空。时间复杂度 O(N log k)，N 是总节点数。

六、优先队列在实际算法中的应用

Dijkstra 最短路径算法：用最小堆每次取出当前距离最小的点。
哈夫曼编码：用最小堆合并两个最小权值的节点。
任务调度：操作系统按优先级调度进程。
数据流中的中位数：用两个堆（最大堆+最小堆）维护。

七、相关知识点指引

堆（Heap）：优先队列的内部实现，分为最大堆和最小堆。学习堆的插入和删除操作。
STL 容器适配器：stack、queue、priority_queue 都是容器适配器，底层依赖 vector 或 deque。
仿函数（函数对象）：自定义比较器时常用，也是 STL 的重要概念。
排序算法：优先队列可以用于实现堆排序。
图论中的 Dijkstra：可能会用到优先队列优化。

总结：优先队列就像一个有“插队特权”的队列，每次让最重要的元素先走。在 C++ 中，priority_queue 默认是最大堆，通过 greater 变成最小堆。对于自定义类型，记得提供比较规则。掌握它，你就能高效地解决很多需要动态优先级的题目！

例题精讲