Lecture 10: 优先队列与二叉堆（Priority Queues & Binary Heaps）（对应课程真实讲座 L18）

目录 · ← l9 · l11 →

Lecture 10: 优先队列与二叉堆（Priority Queues & Binary Heaps）（对应课程真实讲座 L18）

概述

本讲引入第一棵树形结构——二叉最小堆（minheap），并借此实现”优先队列”这个 ADT：元素按优先级出队，而非先进先出。核心问题是如何让”插入”与”取出最小”两个操作都快；答案是利用一棵”完全二叉树 + 父不大于子”的堆，藏在数组里，用上滤/下滤两招在 O(log n) 内完成维护。堆还是堆排序与后续 Dijkstra、Huffman 等算法的心脏。（官方对应：2026 夏季学期 L18，Thursday, July 23 — Priority Queues and Binary Heaps，配有一份手写讲义 minheaps-written-notes.pdf；其中 heapify 与 maxheap 部分官方标注为选学补充。）

核心概念与算法原理

1. 树术语热身（为二叉树铺路）

它是什么：树由节点与连接节点的边组成；每个节点最多一个父、可有多个子；没有父的是根，没有子的是叶；父与子的关系构成子树；从根到最深叶的边数叫高度。若每个节点最多两个子，叫二叉树（区分左孩子/右孩子）。若除最后一层外每层都填满，且最后一层节点全部靠左无空洞，叫完全二叉树（complete binary tree）——它是堆的地基。

2. 二叉最小堆：两条性质

问题定义：想要一种结构同时支持”插入任意值”与”取出最小值”都很快。普通有序数组插入慢，无序数组找最小慢，链表两头不讨好——堆用部分有序换来了两全。

它是什么：最小堆 = 完全二叉树 + 两条性质：①结构性质：完全（逐层从左到右填满）；②堆序性质：任意节点的值 ≤ 其两个孩子（于是也 ≤ 整棵子树）。推论：根永远是全局最小，任何子树的根也是该子树的最小。最大堆（maxheap）只是把 ≤ 换成 ≥，根是最大（官方把 maxheap 列为补充选学，std::priority_queue 默认就是最大堆）。

3. 数组表示：把树”压平”

为什么能压：因为完全二叉树”从左到右无空洞”，按层序遍历放进数组恰好占满下标 0..n-1，没有浪费的洞（官方 L18 特别表扬了这一点）。

 下标:    0     1     2     3     4     5     6
        ┌────┬────┬────┬────┬────┬────┬────┐
 数组   │ 3  │ 5  │ 8  │ 12 │ 7  │ 20 │ 15 │     ← 同一份数据折成树看：
        └────┴────┴────┴────┴────┴────┴────┘

                   3 (0)              ← 根 = 最小值，永远在下标 0
                 /       \
            5 (1)           8 (2)     ← 下标 1、2
           /    \          /    \
      12 (3)   7 (4)    20 (5)  15 (6) ← 叶子/内部节点（括号里是数组下标）

 下标公式（数组从 0 开始）：
   节点 i 的左孩子 = 2i + 1        节点 i 的右孩子 = 2i + 2
   节点 i 的父节点 = (i - 1) / 2    （整数除法）
 例：i=1（值 5）的孩子是 3（12）与 4（7）；i=4（值 7）的父是 (4-1)/2 = 1（值 5）

4. insert：放到末尾，再上滤 percolateUp

操作步骤：① 把新值 push 到数组末尾（树的最左下空位，保持”完全”）；② 与父比较：若比父小就交换上移一层，重复直到不小于父或到达根。官方也叫它 sift up / bubble up（上冒）。

insert(2) 进 [3,5,8,12,7,20,15]：
 ① 末尾追加 → [3, 5, 8, 12, 7, 20, 15, 2]   新值下标 7，父 (7-1)/2=3 → 值 12
 ② 2 < 父12 → 交换 → [3, 5, 8, 2, 7, 20, 15, 12]  新下标 3，父 = 1 → 值 5
 ③ 2 < 父5  → 交换 → [3, 2, 8, 5, 7, 20, 15, 12]  新下标 1，父 = 0 → 值 3
 ④ 2 < 父3  → 交换 → [2, 3, 8, 5, 7, 20, 15, 12]  到达根，停
 上滤路径：12 → 5 → 3，即沿"父链"向上冒；最多走整棵树的高度层。

5. extractMin：取根，末元素补位，再下滤 percolateDown

操作步骤：① 记下根的值（就是最小）；② 把最后一个元素挪到根（保持”完全”）；③ 删掉末尾；④ 与两个孩子中较小者比较，若比它大就换下去，重复到不大于任何孩子或成为叶。必须与”较小的孩子”换：若与较大的换，另一个更小的孩子会违反堆序。

extractMin()（接上例，堆为 [2,3,8,5,7,20,15,12]）：
 ① 返回值 = 2；末元素 12 补到根：→ [12, 3, 8, 5, 7, 20, 15]
 ② 12 与孩子 3、8 比：换较小的 3 → [3, 12, 8, 5, 7, 20, 15]
 ③ 12 与孩子 5、7 比：换较小的 5 → [3, 5, 8, 12, 7, 20, 15]
 ④ 12 的下标 3 已无孩子 → 停。返回的 2 即被删除的最小值。

运行时间：最坏 O(log n)（一路沉到底）；最好 O(1)——补位元素到位即停（如所有值相等，或它已经不大于两个孩子；官方强调堆再大也可能 O(1)）。注意：堆不支持删除任意值——找任意值最坏 O(n)，且删除会破坏”完全”结构难以恢复；需要任意删除时应换别的数据结构。

6. 优先队列（priority queue）扩展

它是什么：把”优先级 + 数据”捆绑成一个节点（如打印任务 = 页数 + 内容），按优先级排堆，数据跟着优先级走。官方举了共享打印机的例子：以页数为优先级，小任务先打印，没人需要等一个要打 500 页的大任务。操作命名上官方给出三组同义词：插入 = enqueue/insert/add；取最小 = dequeue/delete/deleteMin；只看最小 = peek/findMin/getMin。peek 恒为 O(1)：直接看根。

7. 应用：堆排序（heapsort）

思路：① 把 n 个元素逐个 insert 进最小堆：O(n log n)；② 反复 extractMin 并把结果依序放入数组：O(n log n)。第 ② 步出来的值天然升序，总时间 O(n log n)——与归并排序同级，且无需额外大数组做合并（本实现用 vector 存储即 O(n) 空间）。官方把 n 次插入的总代价写成逐项求和：第 k 次插入最坏 O(log k)，总和 log1+log2+…+logn = log(n!) = O(n log n)（斯特林近似）——这个”小心逐项求和”的习惯很重要，因为有些算法（如下面 heapify）按直觉估会错。

8. 补充：heapify 一次建堆为什么是 O(n)（官方列为选学，但值得懂）

把任意数组就地变成堆，做法是从最后一个非叶节点（下标 n/2−1）开始，自底向上逐个 percolateDown，直到根。粗看”n/2 次 × O(log n)”似乎该是 O(n log n)，但树底部的节点下沉距离很短：高度 1 的节点最多沉 1 步、高度 2 的沉 2 步……把每层工作量加起来是几何级数，收敛为 O(n)。教训：对”结构大小在变化”的操作做估算时，逐项求和往往比”单次最坏 × 次数”更准确（官方 L18 专门花篇幅讲了这一点）。

9. 高度推导

完全二叉树第 k 层满员时有 2^k 个节点；含 n 个节点的堆满足 2^h ≤ n < 2^(h+1)，故高度 h = ⌊log₂n⌋——这就是所有堆操作最坏 O(log n) 的来源。

代码示例与实现详解

示例 1：手写 MinHeap 类（std::vector 存储 + insert 上滤 + extractMin 下滤 + heapify 建堆）

#include <iostream>
#include <vector>
#include <algorithm>   // std::swap
#include <stdexcept>   // std::runtime_error
using namespace std;

class MinHeap {
public:
    MinHeap() = default;                          // 空堆
    explicit MinHeap(const vector<int>& values);  // 由任意数组一次建堆（heapify）
    void insert(int value);                       // 插入：末尾 + 上滤
    int extractMin();                             // 取出并删除最小值
    int peek() const { return _data[0]; }         // 只看根（最小）
    int size() const { return static_cast<int>(_data.size()); }
    bool isEmpty() const { return _data.empty(); }
    const vector<int>& data() const { return _data; }  // 教学用：观察内部数组

private:
    vector<int> _data;
    void percolateUp(int index);    // 上滤（bubble up）
    void percolateDown(int index);  // 下滤（bubble down）
};

// heapify：从最后一个非叶节点（n/2-1）开始自底向下滤，总代价 O(n)
MinHeap::MinHeap(const vector<int>& values) : _data(values) {
    for (int i = static_cast<int>(_data.size()) / 2 - 1; i >= 0; i--)
        percolateDown(i);
}

void MinHeap::insert(int value) {
    _data.push_back(value);                          // ① 放到末尾，保持"完全"
    percolateUp(static_cast<int>(_data.size()) - 1); // ② 上滤恢复堆序
}

void MinHeap::percolateUp(int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;                // 父节点公式
        if (_data[index] >= _data[parent]) break;    // 不比父小 → 到位
        swap(_data[index], _data[parent]);           // 比父小 → 与父交换
        index = parent;                              // 上移一层继续
    }
}

int MinHeap::extractMin() {
    if (isEmpty()) throw runtime_error("空堆不可 extractMin");
    int minValue = _data[0];        // ① 最小就是根
    _data[0] = _data.back();        // ② 末元素补到根，保持"完全"
    _data.pop_back();               // ③ 删掉末尾
    if (!_data.empty()) percolateDown(0);  // ④ 下滤恢复堆序
    return minValue;
}

void MinHeap::percolateDown(int index) {
    int n = static_cast<int>(_data.size());
    while (true) {
        int left = 2 * index + 1, right = 2 * index + 2;
        int smallest = index;                       // 在"我、左、右"中找最小
        if (left < n && _data[left] < _data[smallest])  smallest = left;
        if (right < n && _data[right] < _data[smallest]) smallest = right;
        if (smallest == index) break;               // 我已是三者最小 → 到位
        swap(_data[index], _data[smallest]);        // 与较小孩子交换
        index = smallest;
    }
}

int main() {
    MinHeap h;
    for (int v : {42, 17, 33, 5, 90, 1, 55, 8, 21, 3})
        h.insert(v);
    cout << "peek = " << h.peek() << endl;          // 1

    cout << "extractMin 依次取出（天然升序 = 堆排序的雏形）：" << endl;
    while (!h.isEmpty()) cout << h.extractMin() << " ";
    cout << endl;

    MinHeap built(vector<int>{9, 4, 7, 1, 3, 6});   // heapify 一次建堆
    cout << "heapify 后内部数组：";
    for (int v : built.data()) cout << v << " ";    // 1 3 6 4 9 7
    cout << endl;
    cout << "再全部取出：";
    while (!built.isEmpty()) cout << built.extractMin() << " ";  // 1 3 4 6 7 9
    cout << endl;
    return 0;
}

【代码做什么】 main 先逐个 insert 十个数，peek 确认根最小，然后反复 extractMin 得到升序序列——这正是堆排序的两步曲。随后用 heapify 构造器把任意数组 {9,4,7,1,3,6} 一次变成合法最小堆：先打印内部数组可见数组形态变成 {1,3,6,4,9,7}（读者可对照下滤过程自证），再依次取出验证升序。

【实现机制解说】

• insert 的上滤过程：push_back 保证”完全”（数组末尾即最左下空位）；percolateUp 每轮用 (index-1)/2 找父，只与父比——因为堆序性质只需保证”父 ≤ 子”，新值一路上行即可让整条路径恢复有序。终止条件写成 >= 即相等时也停（等值堆一切操作都 O(1)）。
• extractMin 的下滤过程：直接删根会在树顶留”洞”破坏完全性，所以先把末尾元素搬到根再下滤。percolateDown 每轮在 index、left、right 三者中选最小者，只有当”我不是最小”才交换——这保证换完后 父 ≤ 两个孩子 同时成立；若误与较大孩子交换，另一个孩子会变成”父比子大”而再次违规。
• 边界检查是生命线：left < n && right < n 缺一不可，越界读数组是未定义行为（对照上一讲”数组越界不检查”的教训，这里必须自己守边界）。
• heapify 的正确姿势：只能自底向上 percolateDown（从 n/2−1 到 0）；若自顶向下逐个 insert 则是 O(n log n)。原因是”把子树弄成堆”要先保证子树已经是堆，底部的小堆先成立，上层才能一次下沉到位。

示例 2：堆排序函数与 std::priority_queue 用法小示例

官方堆排序配方就是”全部 insert + 依次 extractMin”；示例 1 的弹出循环已是其雏形。下面给出标准库版（自包含可编译）：用 std::priority_queue 的最小堆形态排序，并演示默认最大堆与最小堆的用法差异。

#include <iostream>
#include <vector>
#include <queue>
#include <functional>   // std::greater
using namespace std;

// 标准库最小堆版堆排序：全部 push，再依次 top+pop，出来即升序
vector<int> heapSort(const vector<int>& values) {
    priority_queue<int, vector<int>, greater<int>> pq;  // 最小堆
    for (int v : values) pq.push(v);
    vector<int> sorted;
    while (!pq.empty()) {
        sorted.push_back(pq.top());   // 当前最小
        pq.pop();
    }
    return sorted;
}

int main() {
    vector<int> a = {42, 17, 33, 5, 90, 1, 55, 8};
    vector<int> sorted = heapSort(a);
    cout << "堆排序结果：";
    for (int v : sorted) cout << v << " ";   // 1 5 8 17 33 42 55 90
    cout << endl;

    // 用法对比：priority_queue 默认是大根堆（top 最大）；
    // 模板参数 <类型, 底层容器, 比较器> 换成 greater<int> 即最小堆
    priority_queue<int> maxq;
    priority_queue<int, vector<int>, greater<int>> minq;
    for (int v : a) { maxq.push(v); minq.push(v); }
    cout << "大根堆 top = " << maxq.top() << endl;   // 90
    cout << "最小堆 top = " << minq.top() << endl;   // 1
    maxq.pop();
    cout << "大根堆 pop 后 top = " << maxq.top() << endl;  // 55
    return 0;
}

【代码做什么】 heapSort 把元素全部 push 进最小堆，再循环 top + pop 收集成升序数组。main 演示 priority_queue 的默认形态（最大堆）与换比较器后的最小堆：同样数据，两个堆的 top 分别给出最大 90 与最小 1。

【实现机制解说】

• priority_queue 只暴露 top/push/pop 三个口，没有迭代器、不支持任意删除——这就是”ADT 边界”的体现：底层是堆还是别的结构对调用方透明，接口只承诺”能拿到最大/最小”。
• 比较器方向容易绕晕：greater<int> 让 top 返回最小值。原因：priority_queue 约定”比较器返回 true 表示 a 排在 b 后面/优先级更低”，于是 greater 语义下最小值排最前。官方用最小堆讲原理，而标准库默认给你最大堆——写代码前先想清楚自己到底要最大还是最小。
• 手写 MinHeap 与标准库本质同一算法，差异只在：vector 是”存储 + 堆化”自己管，priority_queue 把”谁是最小/最大”的比较规则参数化了。

复杂度分析

要点：堆的高度 h = ⌊log₂n⌋ 决定一切最坏上界；”重复操作的总代价”要用逐项求和，别用”单次最坏 × 次数”拍脑袋（heapify 就是反例）。

关键要点

• 最小堆 = 完全二叉树 + 堆序（父 ≤ 子），根恒为最小；完全性保证了紧凑的数组表示与三条下标公式（左 2i+1、右 2i+2、父 (i-1)/2）。
• insert 先放末尾再上滤；extractMin 先取根、末元素补位再下滤——两个”滤”都沿树高走，最坏 O(log n)。
• 下滤必须与较小孩子交换；数组访问前务必检查左右孩子下标是否越界。
• 优先队列 = 最小堆 + 优先级数据捆绑：peek O(1)，插入/取最小 O(log n)，不支持任意值删除。
• 堆排序 = n 次 insert + n 次 extractMin，O(n log n)；heapify 自底向上一次建堆只需 O(n)。

常见陷阱与注意事项

• 下标公式记混：从 0 开始时父是 (i-1)/2，孩子是 2i+1/2i+2；把父写成 i/2 或把根当下标 1 都会错位（若坚持下标 1 起，公式会变，务必全程序统一）。
• 下滤时与较大的孩子交换：会让另一个孩子违反堆序；永远选两个孩子中较小者。
• 越界读孩子：percolateDown 里不判 left < n/right < n 就会读数组尾巴外面——行为未定义（对照数组越界的教训）。
• extractMin 忘了”末元素补根”：直接删根留下空洞，完全性被破坏，之后下标公式全部失效。
• 建堆用错方向：逐个 insert 是 O(n log n)；想 O(n) 必须自底向上对非叶节点 percolateDown。
• 手写时忘维护 size：push_back 与 pop_back 之外若自管计数器，加一减一都要与 vector 同步。
• 对空堆 peek/extractMin：先 isEmpty() 再动手；标准库则是先判 empty 再 top/pop。
• priority_queue 默认是大根堆：想要最小堆必须显式传 greater<int>；别想当然以为 top 是最小。
• 把”最好 O(1)”当”总是 O(1)”：插入最坏仍是 O(log n)，均摊分析要逐项求和而不是乘法估算。

思考题（带答案）

问题 1：往一个高度为 4 的最小堆插入 99，什么情况下是最好情形？什么情况下 99 会一路升到根（最坏情形）？根位置的值最小，为什么 99 还能”升”到根？ 答案：若 99 的父节点及祖先都 ≤ 99（例如整棵堆的数值都比 99 小），它一步不升，O(1)——这就是最好情形。注意：堆序只约束”父 ≤ 子”，并不要求树从上到下整体有序，所以完全可能某条”父链”上的值（如 100、150、200）都比 99 大，99 就会一路与父交换升到根，触发最坏 O(log n)。把 99 放进”父链数值很大”的堆即最坏用例。

问题 2：用数组表示堆时，为什么 insert 的新元素总是放”末尾”，extractMin 也总是从”末尾”取补位元素？这两个位置的下标分别怎么算？ 答案：都是为了保住”完全性”——树只能从左到右逐层填满。新元素永远放在最左下第一个空位，即数组当前末尾下标 n（追加后为 n）；补位元素取当前最后一个元素下标 n−1（pop 前）。于是任何时刻数组 0..n−1 都紧凑无洞，下标公式恒成立。

问题 3：heapify 对数组 {9,4,7,1,3,6} 建堆为何是 O(n) 而不是 O(n log n)？请给出你的估算直觉。 答案：自底向上从最后一个非叶节点（n/2−1=2，值 7）开始下滤，最终得到 {1,3,6,4,9,7}。耗时关键在：接近叶子的节点（数量多）下沉距离短（1 步、2 步），只有靠近根的少数节点才可能沉满 log n 步；把”节点数 × 各自下沉距离”按层求和是一个收敛的几何级数，总量 O(n)。若反过来自顶向下逐个 insert，每个新节点都可能上滤满高度，才是 O(n log n)——”单次最坏 × 次数”的直觉在这里恰好失效。