我的算法书 - 堆

一句话算法

二叉堆把极值放在根上：插入时向上浮，删除堆顶时把末尾补到根再向下沉。

问题模型

堆用于动态维护一个集合的最小值或最大值。最常见操作是：

push(x)：插入一个元素；
top()：查询当前最小值或最大值；
pop()：删除当前最小值或最大值。

本文以小根堆为例，堆顶总是当前最小值。

二叉堆结构

二叉堆是一棵满足堆性质的完全二叉树。

小根堆性质：

father \le left,\quad father \le right

因为它是完全二叉树，所以可以用数组紧凑存储。下标从 1 开始时：

\begin{aligned} left(i) &= 2i \\ right(i) &= 2i+1 \\ father(i) &= \lfloor i/2 \rfloor \end{aligned}

这样不需要显式存指针。

核心直觉

插入：向上浮

新元素先放到数组末尾，也就是完全二叉树的最后一个位置。

如果它比父亲更小，就破坏了小根堆性质。把它和父亲交换，继续向上检查。

新来的小值像气泡一样往上浮，直到父亲不比它大。

删除堆顶：向下沉

删除根以后，为了保持完全二叉树形状，用最后一个元素补到根。

这个元素可能比孩子更大，所以要和两个孩子中更小的那个交换，继续向下调整。

根上的大值像石头一样往下沉，每次沉向更小的孩子。

算法步骤

插入 `push(x)`

把 x 放到数组末尾。
设当前位置为 u。
如果 u > 1 且 h[u] < h[u / 2]，交换它和父亲。
重复直到到达根，或父亲已经不大于它。

删除堆顶 `pop()`

用最后一个元素覆盖根。
删除数组末尾。
从根开始执行 down。
每次选择左右孩子中更小的那个。
如果孩子比当前节点更小，就交换并继续；否则停止。

算法证明

核心不变量：除了当前正在调整的节点外，其它位置都满足堆性质。

插入正确性

新元素插入到末尾，只可能破坏它和父亲之间的关系。
如果新元素不小于父亲，堆性质已经恢复。
如果新元素小于父亲，交换它们后：
- 新元素上移，可能继续和新的父亲冲突；
- 原父亲下移到子节点位置，因为它原来不大于其它孩子，且现在替换的是更小的子节点位置，不会破坏下面子树的相对结构。
重复这个过程，直到冲突消失。

因此 up 能恢复插入后的堆性质。

删除堆顶正确性

删除根后，用最后一个元素补到根，只可能破坏根到某条向下路径上的堆性质。
如果当前节点不大于两个孩子，调整结束。
如果它大于某个孩子，必须和更小的孩子交换。因为更小的孩子放到当前位置后，能同时不大于另一个孩子。
交换后，问题只可能出现在被换下去的那个子树根上。

因此 down 能恢复删除后的堆性质。

复杂度分析

完全二叉树高度为：

O(\log n)

所以：

push 时间复杂度： $O(\log n)$ ；
pop 时间复杂度： $O(\log n)$ ；
top 时间复杂度： $O(1)$ ；
空间复杂度： $O(n)$ 。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

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

template <typename T>
struct MinHeap {
    // h[0] 不使用，让父子下标关系保持为 u/2、u*2、u*2+1。
    vector<T> h;

    MinHeap() {
        h.push_back(T());
    }

    int size() const {
        return (int)h.size() - 1;
    }

    bool empty() const {
        return size() == 0;
    }

    T top() const {
        return h[1];
    }

    void up(int u) {
        while (u > 1 && h[u] < h[u / 2]) {
            swap(h[u], h[u / 2]);
            u /= 2;
        }
    }

    void down(int u) {
        while (true) {
            int best = u;
            int left = u * 2;
            int right = u * 2 + 1;

            if (left <= size() && h[left] < h[best]) best = left;
            if (right <= size() && h[right] < h[best]) best = right;
            if (best == u) break;

            swap(h[u], h[best]);
            u = best;
        }
    }

    void push(const T &x) {
        h.push_back(x);
        up(size());
    }

    void pop() {
        if (empty()) return;
        h[1] = h.back();
        h.pop_back();
        if (!empty()) down(1);
    }
};

int main() {
    int n;
    cin >> n;

    MinHeap<int> heap;
    while (n--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            heap.push(x);
        } else if (op == 2) {
            cout << heap.top() << "\n";
        } else if (op == 3) {
            heap.pop();
        }
    }

    return 0;
}

测试用例

输入：

输出：

3
5
1

应用分类详解

堆的本质是动态维护集合极值。它适合“不断加入元素，并且总要取出当前最小/最大”的问题。

一、动态集合极值

典型模式： 集合不断变化，每次查询当前最小值或最大值。

识别信号： 出现“插入”“删除最小值”“查询最小值”“优先级最高的任务”。

核心建模： 把元素放进堆，堆顶就是当前极值。

应用场景	经典题目	核心思路
堆模板	luogu-P3378	支持插入、查询最小值、删除最小值
数据流第 K 大	LeetCode 703	维护大小为 K 的小根堆

二、贪心中的反悔

典型模式： 先按顺序做选择，后面遇到更优选择时替换掉当前已选集合中最差的一个。

识别信号： 出现“最多选若干个”“总容量限制”“如果超了就删掉代价最大的”。

核心建模： 堆保存已选元素中最应该被替换的那个。

应用场景	经典题目	核心思路
课程表 III	LeetCode 630	超时后删掉耗时最长课程
反悔贪心	常见 CF 题	堆顶保存当前最差选择

三、图论最短路

典型模式： 每次取出当前距离最小的状态继续扩展。

识别信号： 出现“带权图最短路”“每次选择当前最近点”。

核心建模： Dijkstra 用小根堆维护待扩展节点，堆顶是当前最短候选距离。

应用场景	经典题目	核心思路
Dijkstra 优化	最短路专题	用堆把取最小距离从 $O(n)$ 优化到 $O(\log n)$
A* 搜索	搜索专题	用优先队列按估价函数扩展

四、多路归并和哈夫曼合并

典型模式： 多个有序来源中反复取最小，或每次合并最小的两个元素。

识别信号： 出现“合并 K 个有序序列”“每次取最小两个合并”“总代价最小”。

核心建模： 堆维护所有当前候选，弹出最小后把新候选放回。

应用场景	经典题目	核心思路
合并果子	luogu-P1090	每次合并最小的两堆
合并 K 个升序链表	LeetCode 23	堆中保存每条链表当前头节点

经典例题

1. luogu-P3378

小根堆模板题。直接练习 push、top、pop 三个操作。

2. luogu-P1090

合并果子。每次取出最小的两堆合并，再把新堆放回，是哈夫曼式贪心。

3. Dijkstra 最短路

堆不是最短路本身，但它能高效维护“当前距离最小的待扩展节点”，是稀疏图 Dijkstra 的关键优化。

参考

本文旧版解析保留的核心思路：二叉堆用完全二叉树维护根节点极值，调整只沿一条父子链进行。