优先队列（priority_queue）：让最“重要”的元素先走

这是什么？用来干啥？

想象一下：你正在电影院排队买票，突然来了一个持有VIP票的人，他可以直接走到最前面买票，不用排长队。或者，你在医院急诊室，一位生命垂危的病人会被医生优先救治，即使他来得比其他人晚。这就是“优先级”——谁更重要，谁先被服务。

在编程中，我们经常遇到类似场景：有一堆任务，有的紧急（比如“交作业截止时间快到了”），有的不紧急（比如“打游戏”）。如果我们把任务放进一个普通队列，它们会按“先来后到”的顺序执行，这显然不合理。优先队列就是为了解决这个问题而生的。它像一个“智能”的队列：你把元素放进去，它会根据优先级自动排列。你要取出元素时，总是取出当前优先级最高的那一个。

优先队列的底层实现通常是堆（一种特殊的树形数据结构），这使得插入和删除“最值”都非常高效（时间复杂度 O(log n)），而查看优先级最高的元素只需要 O(1) 时间。

在 C++ 中，STL 提供了 priority_queue，默认是最大堆——也就是优先级最高的元素（数值最大）最先出队。在 Python 中，标准库的 heapq 模块实现了最小堆（数值最小的最先出队），但我们可以通过技巧让它变成最大堆。

生活中的更多例子

操作系统进程调度：操作系统会优先运行优先级高的程序（比如你正在看的视频播放器），而让后台下载任务靠后。
下载管理器：你可以设置某个文件“优先下载”，它就会排在其他文件前面。
游戏中的BOSS战：玩家对BOSS造成伤害时，伤害最高的玩家往往有资格获得掉落奖励的优先权。
急救分级：医院急诊对病人按病情严重程度分级，危重病人优先救治。

这些场景的共同点：我们需要一个容器，能快速找到并弹出“最紧急”或“最重要”的元素。

C++ STL 中的 priority_queue

原理快速回顾

priority_queue 是一个容器适配器（Container Adapter），它内部使用一个容器（默认是 vector）来存储元素，并通过堆算法维护顺序。当你 push 一个新元素时，它会上浮到合适的位置；当你 pop 时，堆顶元素（优先级最高）被移除，然后新的堆顶会浮上来。

模板定义

#include <queue>   // priority_queue 也在 queue 头文件中

template<
    class T,                        // 元素类型
    class Container = std::vector<T>, // 底层容器，默认 vector
    class Compare = std::less<typename Container::value_type> // 比较器，默认 less（最大堆）
> class priority_queue;

T：元素类型，比如 int、double、自定义的结构体。
Container：存元素的容器，必须支持 random access（随机访问），比如 vector 或 deque。一般我们用默认的 vector。
Compare：比较函数对象。less 表示“越大的元素优先级越高”（最大堆）；greater 表示“越小的元素优先级越高”（最小堆）。

函数	作用	时间复杂度
`push(x)`	插入元素 x	O(log n)
`pop()`	删除堆顶元素（优先级最高）	O(log n)
`top()`	返回堆顶元素的引用	O(1)
`empty()`	判断是否为空	O(1)
`size()`	返回元素个数	O(1)

三种典型用法

1. 最大堆（默认）

默认就是最大堆，适合求“最大的元素”优先。

#include <iostream>
#include <queue>   // 包含 priority_queue

using namespace std;

int main() {
    // 定义一个最大堆，元素类型为 int
    priority_queue<int> pq;  // 等价于 priority_queue<int, vector<int>, less<int>>

    // 插入一堆数字
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);
    pq.push(40);

    cout << "当前队列大小: " << pq.size() << endl;   // 输出 5
    cout << "优先级最高的元素: " << pq.top() << endl; // 输出 50

    // 依次弹出所有元素，观察顺序
    cout << "按优先级从高到低输出: ";
    while (!pq.empty()) {
        cout << pq.top() << " ";  // 输出当前最大值
        pq.pop();                 // 弹出后堆调整
    }
    cout << endl; // 输出 50 40 30 20 10

    return 0;
}

2. 最小堆（使用 greater）

想让最小的元素最先出队？用 greater<int> 作为比较器。

#include <iostream>
#include <queue>
#include <vector>   // 需要显示指定底层容器

using namespace std;

int main() {
    // 最小堆：三个参数：元素类型、底层容器、比较器
    priority_queue<int, vector<int>, greater<int>> minpq;

    minpq.push(30);
    minpq.push(10);
    minpq.push(50);
    minpq.push(20);
    minpq.push(40);

    cout << "最小值: " << minpq.top() << endl; // 输出 10

    cout << "按优先级从低到高输出: ";
    while (!minpq.empty()) {
        cout << minpq.top() << " ";
        minpq.pop();
    }
    cout << endl; // 输出 10 20 30 40 50

    return 0;
}

3. 自定义类型——按你自己的规则排序

比如我们有一个“任务”结构体，包含名称和优先级（数值越大越紧急）。我们希望紧急的任务优先出队。这时需要自定义比较器。

方法一：重载 operator<
由于 priority_queue 默认使用 less，它会调用元素的 operator< 来判断大小。如果我们想让优先级大的元素排在堆顶（即视为“小”的反而在下面？），实际上我们需要定义：a < b 当且仅当 a.priority < b.priority。这样，less 认为优先级大的元素“不小于”优先级小的，于是优先级大的在堆顶。代码：

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

using namespace std;

struct Task {
    string name;
    int priority;  // 数值越大越紧急

    // 重载 <，注意 const 和 const 修饰符
    bool operator<(const Task& other) const {
        // 我们希望 priority 大的排在前面，所以让大的“小于”小的？不对！
        // 实际上 less 期望 a < b 返回 true 表示 a 应该排在 b 之后（即 b 优先级更高）。
        // 但为了简单，我们直接按 priority 比较：priority 大的视为“更大”，
        // 而 less 会让“更大”的留在堆顶。所以这里就写 priority < other.priority。
        return priority < other.priority;
    }
};

int main() {
    priority_queue<Task> pq;

    // 插入任务，使用 Task 的构造函数初始化
    pq.push(Task{"写作业", 3});
    pq.push(Task{"吃饭", 5});
    pq.push(Task{"打游戏", 1});
    pq.push(Task{"睡觉", 2});
    pq.push(Task{"紧急会议", 10});

    while (!pq.empty()) {
        Task t = pq.top();  // 获取优先级最高的任务
        cout << t.name << " (优先级:" << t.priority << ")" << endl;
        pq.pop();
    }

    return 0;
}

输出：

紧急会议 (优先级:10)
吃饭 (优先级:5)
写作业 (优先级:3)
睡觉 (优先级:2)
打游戏 (优先级:1)

方法二：使用仿函数（函数对象）作为比较器
如果你不想修改结构体本身的 operator<，可以单独定义一个比较类。

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

using namespace std;

struct Task {
    string name;
    int priority;
};

// 定义一个比较结构体，用于 priority_queue
struct CompareTask {
    bool operator()(const Task& a, const Task& b) {
        // 返回 true 表示 a 的优先级比 b 低（a 应该排在 b 后面）
        // 我们希望 priority 大的优先，所以当 a.priority < b.priority 时，a 应该后出
        // 但注意：priority_queue 的比较器含义与 sort 相反，这里直接按“优先级大的在前”写：
        return a.priority < b.priority;  // 优先级大的在堆顶
    }
};

int main() {
    // 第三个参数是自定义比较器
    priority_queue<Task, vector<Task>, CompareTask> pq;

    pq.push({"写作业", 3});
    pq.push({"吃饭", 5});
    pq.push({"打游戏", 1});
    pq.push({"睡觉", 2});
    pq.push({"紧急会议", 10});

    while (!pq.empty()) {
        Task t = pq.top();
        cout << t.name << " (优先级:" << t.priority << ")" << endl;
        pq.pop();
    }

    return 0;
}

输出同上。

特别提醒：自定义比较器时，比较函数的写法容易搞反。记住：priority_queue 默认是最大堆，比较器 Compare 的语义是“如果 a 应该排在 b 之后则返回 true”。所以如果你想让最小的元素在堆顶（最小堆），就比较 a > b；如果你想让最大的在堆顶（最大堆），就比较 a < b（实际就是默认的 less）。如果自己写仿函数，要小心逻辑！

Python 中的实现：heapq 和 PriorityQueue

Python 标准库提供了两种方式实现优先队列：

heapq：轻量级，只支持最小堆，是竞赛和一般开发的首选。
queue.PriorityQueue：基于 heapq 实现，线程安全，适合多线程场景。

我们主要讲 heapq。

最小堆（默认）

import heapq

def main():
    # 创建一个空列表，当作堆
    heap = []

    # 插入元素
    heapq.heappush(heap, 30)
    heapq.heappush(heap, 10)
    heapq.heappush(heap, 50)
    heapq.heappush(heap, 20)
    heapq.heappush(heap, 40)

    print("最小值:", heap[0])  # 10

    # 依次弹出最小元素
    print("从小到大输出:", end=" ")
    while heap:
        print(heapq.heappop(heap), end=" ")
    print()  # 输出 10 20 30 40 50

if __name__ == "__main__":
    main()

模拟最大堆（取反法）

因为 heapq 只支持最小堆，我们可以把数值取负存入，取出时再取反，这样最小值（负数最小）实际上对应原来的最大值。

import heapq

def main():
    heap = []
    heapq.heappush(heap, -30)
    heapq.heappush(heap, -10)
    heapq.heappush(heap, -50)
    heapq.heappush(heap, -20)
    heapq.heappush(heap, -40)

    print("最大值:", -heap[0])  # 50

    print("从大到小输出:", end=" ")
    while heap:
        print(-heapq.heappop(heap), end=" ")
    print()  # 输出 50 40 30 20 10

if __name__ == "__main__":
    main()

自定义优先级（用元组）

如果元素本身有多个属性，我们可以在堆中存储 (priority, item) 元组，heapq 会先按元组的第一个元素排序。这就是实现“有优先级”的常用方法。

import heapq

def main():
    tasks = []
    heapq.heappush(tasks, (3, "写作业"))
    heapq.heappush(tasks, (5, "吃饭"))
    heapq.heappush(tasks, (1, "打游戏"))
    heapq.heappush(tasks, (2, "睡觉"))
    heapq.heappush(tasks, (10, "紧急会议"))

    while tasks:
        priority, name = heapq.heappop(tasks)
        print(f"{name} (优先级:{priority})")

if __name__ == "__main__":
    main()

输出（注意：heapq 是最小堆，所以优先级数值小的先出）：

打游戏 (优先级:1)
睡觉 (优先级:2)
写作业 (优先级:3)
吃饭 (优先级:5)
紧急会议 (优先级:10)

如果你想要最大堆（优先级大的先出），可以用取反法：堆里存 (-priority, item)。

新手最容易犯的 5 个错误

忘记包含头文件
C++ 中 priority_queue 定义在 <queue> 中，不是 <priority_queue>。很多人记得 queue，但忘了加。
✅ 正确：#include <queue>
混淆比较器的方向
自定义比较器时，C++ 的 priority_queue 和 sort 的比较器含义相反。在 sort 中，a < b 表示升序；在 priority_queue 中，a < b 表示 b 的优先级比 a 高（即 a 应该排在 b 之后）。
如果你想让最小的在堆顶，比较器应该返回 a > b。
✅ 记住口诀：默认 less 就是最大堆。要最小堆就用 greater<T>。
试图直接遍历内部元素
priority_queue 不提供迭代器，你不能用 for(auto x : pq) 或者下标访问。唯一能看到的元素就是 top()。
✅ 如果需要查看所有元素，只能一个一个 pop 出来，或者转存到其他容器。
在 C++ 中忽略第三个模板参数
当你要用最小堆时，必须显式写出三个参数：priority_queue<int, vector<int>, greater<int>>。只写 greater<int> 是不行的，因为第二个参数（底层容器）不是默认的？实际上默认是 vector<T>，但第三个参数需要写全，因为模板参数有顺序。可以写成 priority_queue<int, vector<int>, greater<int>>。
在 Python 中误用 queue.PriorityQueue
queue.PriorityQueue 是线程安全的，但它的 put 和 get 方法比 heapq 慢得多。在非多线程场景（如算法竞赛），请直接用 heapq。

完整可运行的代码示例（C++ 综合）

下面是一个完整的程序，展示最大堆、最小堆、自定义类型的三种用法，并包含输入输出：

#include <iostream>
#include <queue>
#include <vector>
#include <string>

using namespace std;

struct Student {
    string name;
    int score;  // 分数越高越优秀
};

// 自定义比较器：分数高的优先（最大堆）
struct CompareScore {
    bool operator()(const Student& a, const Student& b) {
        return a.score < b.score;  // 分数大的在堆顶
    }
};

int main() {
    // 1. 最大堆（默认）
    cout << "=== 最大堆（默认） ===" << endl;
    priority_queue<int> max_pq;
    max_pq.push(30);
    max_pq.push(10);
    max_pq.push(50);
    max_pq.push(20);
    max_pq.push(40);
    cout << "堆顶: " << max_pq.top() << endl; // 50
    cout << "元素个数: " << max_pq.size() << endl;
    cout << "依次弹出: ";
    while (!max_pq.empty()) {
        cout << max_pq.top() << " ";
        max_pq.pop();
    }
    cout << endl << endl;

    // 2. 最小堆（使用 greater）
    cout << "=== 最小堆（greater） ===" << endl;
    priority_queue<int, vector<int>, greater<int>> min_pq;
    min_pq.push(30);
    min_pq.push(10);
    min_pq.push(50);
    min_pq.push(20);
    min_pq.push(40);
    cout << "堆顶: " << min_pq.top() << endl; // 10
    cout << "依次弹出: ";
    while (!min_pq.empty()) {
        cout << min_pq.top() << " ";
        min_pq.pop();
    }
    cout << endl << endl;

    // 3. 自定义类型（按分数最高优先）
    cout << "=== 自定义类型（分数高优先） ===" << endl;
    priority_queue<Student, vector<Student>, CompareScore> student_pq;
    student_pq.push({"小明", 85});
    student_pq.push({"小红", 92});
    student_pq.push({"小刚", 78});
    student_pq.push({"小丽", 95});
    student_pq.push({"小强", 88});

    cout << "按分数从高到低输出：" << endl;
    while (!student_pq.empty()) {
        Student top = student_pq.top();
        cout << top.name << " 分数:" << top.score << endl;
        student_pq.pop();
    }

    return 0;
}

运行结果：

=== 最大堆（默认） ===
堆顶: 50
元素个数: 5
依次弹出: 50 40 30 20 10 

=== 最小堆（greater） ===
堆顶: 10
依次弹出: 10 20 30 40 50 

=== 自定义类型（分数高优先） ===
按分数从高到低输出：
小丽 分数:95
小红 分数:92
小强 分数:88
小明 分数:85
小刚 分数:78

常见应用场景（帮你举一反三）

求数据流中的中位数
用两个堆：一个最大堆存较小的一半，一个最小堆存较大的一半，保持平衡。每来一个新数，根据大小插入适当堆，再调整。中位数就是两个堆顶的平均（或较大堆顶）。
Top K 问题
求数组里最大的 K 个数？维护一个大小为 K 的最小堆。遍历数组，如果堆不满就插入；否则如果当前数比堆顶大，就弹出堆顶再插入当前数。最后堆里就是最大的 K 个数。
求最小的 K 个数？用最大堆，同样方法。
合并 K 个有序链表
每个链表的头节点放入最小堆（按节点值排序），然后不断弹出最小节点，将它的 next 入堆，直到堆空。这样就能得到合并后的有序列表。
Dijkstra 最短路径算法
每次从未确定最短路径的节点中选距离最小的，这正是一个最小堆的应用。优先队列让复杂度从 O(n²) 降到 O((n+m)logn)（n 为节点数，m 为边数）。
任务调度
操作系统或游戏中的任务队列，按紧急程度或剩余时间排序，优先执行最紧急的。

priority_queue优先队列——VIP插队的“自动排序”魔法