CC++ & Algorithm

优先队列（STL priority_queue）

中等3
语言版本：通用
概述：介绍C++ STL中的priority_queue和Python中的heapq模块，它们都基于堆实现。学习如何快速使用优先队列解决最大值/最小值问题。

为什么需要优先队列？排队看病的故事

同学们，你们生病去医院时，是不是要排队挂号？如果是普通感冒，就得按先来后到排队；但如果突然来了一位急诊病人，医生会立刻给他治疗，不管后面排了多少人。这就是“优先级”的概念：每个人有一个紧急程度（优先级），紧急的人可以插队。

在计算机里，很多场景也需要这样的规则：

  • 操作系统处理任务，高优先级的进程先执行
  • 网络路由器转发数据包，紧急的包先发
  • 学校安排活动，重要的会议先开始

优先队列就是专门用来处理这类问题的数据结构。它保证：每次取出的元素，都是当前所有元素中优先级最高（或最低）的。而**堆（Heap）**是计算机中最常用的实现方式，因为它插入和删除都非常快（只需要 O(log n) 步）。

优先队列怎么工作？堆的秘密

堆是一种特殊的二叉树，它有两种形式：

  • 大根堆：爸爸的数值比两个儿子都大。这样堆顶就是最大值。
  • 小根堆：爸爸的数值比两个儿子都小。这样堆顶就是最小值。

当我们往堆里插入一个新元素时，它会自动调整位置，让堆的性质不被破坏。比如在大根堆里，新元素如果比爸爸大，就跟爸爸交换，一直往上“冒泡”，直到找到正确的位置。删除堆顶时，先取走堆顶，然后把最后一个元素放到堆顶，再让它“下沉”到正确位置。

这种“自动排好序”的特性，让优先队列能高效工作。并且，C++ 和 Python 都已经帮我们封装好了，直接调用就行。

重点一：C++ 中的 priority_queue

C++ 标准库的 priority_queue 就像一个自动排序的盒子，你往里面丢东西，每次取出的都是最大（或最小）的那个。默认是一个大根堆（最大值在顶部）。

基本用法

#include <iostream>
#include <queue>      // 必须包含这个头文件
#include <vector>
using namespace std;

int main() {
    // 创建一个优先队列，默认大根堆（最大值优先）
    priority_queue<int> pq;

    // 插入元素：push() 会自动排好序
    pq.push(5);   // 插入 5
    pq.push(1);   // 插入 1
    pq.push(9);   // 插入 9
    pq.push(3);   // 插入 3
    pq.push(7);   // 插入 7

    // 现在堆顶应该是 9
    cout << "堆顶元素（最大值）: " << pq.top() << endl; // 输出 9

    // 依次取出所有元素，从大到小
    cout << "大根堆依次取出（从大到小）: ";
    while (!pq.empty()) {
        cout << pq.top() << " "; // 访问队首（不删除）
        pq.pop();                // 删除队首
    }
    cout << endl;

    return 0;
}

如何得到小根堆（最小值优先）

只需要在定义时加一个参数 greater<int>，就像告诉它“我要让小的排在前面”。

// 小根堆：最小值优先
priority_queue<int, vector<int>, greater<int>> minpq;
minpq.push(5);
minpq.push(1);
minpq.push(9);
minpq.push(3);
minpq.push(7);

cout << "小根堆依次取出（从小到大）: ";
while (!minpq.empty()) {
    cout << minpq.top() << " "; // 输出: 1 3 5 7 9
    minpq.pop();
}

如果你有复杂的数据（比如结构体或自定义类），可以自己写一个比较函数。例如一个学生类，想按成绩排序：

struct Student {
    string name;
    int score;
};

// 自定义比较器：让分数高的学生优先
struct CompareScore {
    bool operator()(const Student& s1, const Student& s2) {
        return s1.score < s2.score;  // 返回 true 表示 s1 优先级低于 s2（大根堆）
    }
};

priority_queue<Student, vector<Student>, CompareScore> pq;

常用操作速查

操作作用时间复杂度
push(val)插入一个元素O(log n)
pop()删除堆顶元素O(log n)
top()获得堆顶元素（不删除）O(1)
empty()判断是否为空O(1)
size()返回元素个数O(1)

重点二：Python 中的 heapq 模块

Python 的 heapq 没有封装成“容器类”，而是直接对列表操作。它默认是小根堆（最小值在顶部）。

小根堆（默认）

import heapq

# 创建一个空列表作为堆
min_heap = []

# 插入元素
heapq.heappush(min_heap, 5)  # 插入 5
heapq.heappush(min_heap, 1)  # 插入 1
heapq.heappush(min_heap, 9)  # 插入 9
heapq.heappush(min_heap, 3)  # 插入 3
heapq.heappush(min_heap, 7)  # 插入 7

print("堆顶元素（最小值）:", min_heap[0])  # 输出 1（列表索引0就是堆顶）

# 依次取出所有元素，从小到大
print("小根堆依次取出（从小到大）: ", end="")
while min_heap:
    print(heapq.heappop(min_heap), end=" ")  # 每次弹出最小值
print()  # 输出: 1 3 5 7 9

如何得到大根堆（最大值优先）

因为 Python 的 heapq 只支持小根堆，我们可以插入负数来模拟。比如想存 5，实际存 -5。取出时再变回正数。这样负数的“最小值”对应的其实是原数的最大值。

import heapq

max_heap = []
heapq.heappush(max_heap, -5)  # 存 -5，代表放入了 5
heapq.heappush(max_heap, -1)  # 存 -1，代表放入了 1
heapq.heappush(max_heap, -9)  # 存 -9，代表放入了 9
heapq.heappush(max_heap, -3)  # 存 -3，代表放入了 3
heapq.heappush(max_heap, -7)  # 存 -7，代表放入了 7

print("堆顶元素（最大值的负数）:", max_heap[0])  # 输出 -9（因为 -9 最小，对应原数 9 最大）
# 取出时取负恢复
print("大根堆依次取出（从大到小）: ", end="")
while max_heap:
    print(-heapq.heappop(max_heap), end=" ")  # 输出: 9 7 5 3 1
print()

如果一开始就有一个列表，想把它变成堆，可以用 heapq.heapify()。

arr = [4, 10, 3, 5, 1]
heapq.heapify(arr)  # 把 arr 原地变成小根堆
print("建堆后的数组:", arr)  # 输出类似 [1, 4, 3, 5, 10]

常用操作速查

操作作用时间复杂度
heapq.heappush(heap, val)插入元素O(log n)
heapq.heappop(heap)弹出并返回最小值O(log n)
heap[0]访问堆顶（不删除）O(1)
heapq.heapify(list)将列表原地转为堆O(n)
heapq.heappushpop(heap, val)先插入再弹出，效率高O(log n)
heapq.nlargest(k, iterable)返回前 k 大的元素O(n log k)
heapq.nsmallest(k, iterable)返回前 k 小的元素O(n log k)

（注意：heapq.nlargest 和 nsmallest 并不是用堆来实现全排序，而是用堆高效拿到前 k 个。）

新手容易犯的错误 ❌

错误1：忘记包含头文件（C++）

使用 priority_queue 必须包含 <queue>，写 #include <queue>。如果不写，编译器会报错。

错误2：pop() 后继续访问 top()

priority_queue<int> pq;
pq.push(10);
pq.pop();
cout << pq.top();  // 出错！队列已空

解决方法：先判断 !pq.empty()。

错误3：用 greater 时漏写参数

// 正确写法
priority_queue<int, vector<int>, greater<int>> minpq;
// 错误：只写 greater<int> 会报错，因为需要指定底层容器（默认 vector）

所以要写成三部分：类型、底层容器、比较器。

错误4：Python 大根堆忘记取负

max_heap = []
heapq.heappush(max_heap, 5)   # 这样其实是小根堆！

如果想做大根堆，必须存 -5，取时 -heapq.heappop(max_heap)。

错误5：在堆中修改元素

堆只能通过 push 和 pop 操作，如果直接修改了列表中的某个值，堆的性质就被破坏了。 不要这样做：

heap = [1, 3, 2]
heapq.heapify(heap)
heap[0] = 100  # 错误！破坏了堆结构

完整可运行示例：求考试分数的前 3 名

假设班里有 8 个同学，分数分别是 [72, 88, 91, 65, 84, 99, 77, 82]。我们想找出分数最高的 3 个人。用优先队列可以轻松解决：把小根堆的大小固定为 3，每次有新分数就插入，如果堆大小超过 3，就弹出最小的（即当前最小的高分）。这样最后堆里剩下的就是前 3 大的分数。

C++ 版本

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

int main() {
    vector<int> scores = {72, 88, 91, 65, 84, 99, 77, 82}; // 所有分数
    int k = 3; // 要找前3名

    // 小根堆，用于保留最大的k个数
    priority_queue<int, vector<int>, greater<int>> min_heap;

    for (int score : scores) { // 遍历每个分数
        min_heap.push(score);  // 先插入
        if (min_heap.size() > k) { // 如果堆中元素超过k个
            min_heap.pop();    // 弹出最小的那个，保留较大的
        }
    }

    // 打印结果（堆里剩下的是最大的k个数，但顺序不一定是降序）
    cout << "前" << k << "名分数（从大到小）: ";
    vector<int> result;
    while (!min_heap.empty()) {
        result.push_back(min_heap.top()); // 取出堆顶（当前最小）
        min_heap.pop();
    }
    // 因为是小根堆，取出是从小到大，所以要翻转
    for (int i = result.size() - 1; i >= 0; --i) {
        cout << result[i] << " "; // 输出: 99 91 88
    }
    cout << endl;

    return 0;
}

Python 版本

import heapq

scores = [72, 88, 91, 65, 84, 99, 77, 82]  # 所有分数
k = 3  # 要找前3名

# 小根堆，保留最大的k个数
min_heap = []
for score in scores:
    heapq.heappush(min_heap, score)  # 插入分数
    if len(min_heap) > k:            # 如果堆中元素超过k个
        heapq.heappop(min_heap)      # 弹出最小的那个，保留较大的

# 堆里剩下的是最大的k个数，但顺序是小到大
# 我们要从大到小输出，可以倒序
result = sorted(min_heap, reverse=True)  # 对堆排序（只有3个，很快）
print(f"前{k}名分数（从大到小）:", result)  # 输出: [99, 91, 88]

这个思路就是经典的 Top K 问题，用固定大小的堆，时间复杂度 O(n log k)，比全部排序 O(n log n) 快很多。

总结与拓展

内容要点
优先队列一种数据结构，每次取出的元素都是当前优先级最高（或最低）的。
底层实现堆（完全二叉树），插入和删除都是 O(log n)。
C++ priority_queue默认大根堆；用 greater<int> 变成小根堆；可自定义比较器。
Python heapq默认小根堆；用负数模拟大根堆；heapify 可原地建堆。
常见应用合并K个有序链表、Top K 问题、Dijkstra 最短路径、事件模拟等。

如果你对堆本身的原理感兴趣，可以看看堆排序（堆的排序应用）。如果你想挑战更复杂的问题，可以学习可并堆（左偏树）或斐波那契堆（更高效但实现复杂）。在算法竞赛中，优先队列几乎是必备工具，熟练掌握它会让你的解题能力大幅提升！

例题精讲

1单选题

在C++ STL中，priority_queue 默认的底层容器和比较器分别是什么？

Adeque, less<int>
Bvector, less<int>
Cvector, greater<int>
Ddeque, greater<int>
2单选题

关于优先队列（priority_queue）的操作，下列说法正确的是？

Apush() 和 pop() 的时间复杂度均为 O(n)
Btop() 可以访问优先级最低的元素
Cempty() 返回队列中元素的个数
Dpop() 移除的是优先级最高的元素
3判断题

在 Python 中，heapq 模块实现的 heapq.heappop(heap) 操作会弹出并返回堆中最小的元素。

4填空题
以下 C++ 代码使用 priority_queue 实现一个用于求第 K 大元素的小顶堆，请补全声明语句：
priority_queue<int, ___, ___> pq;
5填空题
给定一个整数列表 nums，请使用 Python 的 heapq 模块找出其中最大的 3 个数，补全代码：
result = heapq.______(3, nums)