队列我们都熟：先进先出，队头永远是来得最早的那一个。可现实往往不按先来后到——急诊室里重伤员优先，操作系统里短作业优先，Dijkstra 最短路里"当前距离最小"的节点优先。我们需要一种"按优先级出队，而不是按到达顺序"的结构，这就是优先队列（Priority Queue）；而它最高效的数组实现，叫二叉堆（binary heap）。

本篇讲清三件事：堆长什么样、插入/取最小怎么 O(log n) 完成、以及它和排序、图算法的关系。

一、是什么：堆不是"排好序的数组"

一句话：二叉堆是一棵"完全二叉树"，满足堆序性质（heap property）——每个节点的值都不大于（最小堆）或不小于（最大堆）它的孩子。

  • 完全二叉树：除最后一层外全满，最后一层从左往右填。这个形状让它能紧凑地存进数组，不需要指针。
  • 堆序性质：最小堆里，父 ≤ 子，所以全局最小值一定在堆顶（下标 0）。最大堆反过来。
最小堆（树视图 = 数组视图） 2 5 7 9 11 数组 2 5 7 9 11 0 1 2 3 4

数组下标的关系（0-based）：节点 i 的父是 (i-1)/2，左子是 2i+1，右子是 2i+2。不需要指针，纯靠下标算亲戚。

坑①：堆不是有序数组！它只保证"父 ≤ 子"，同一层的兄弟之间没有任何大小约束。所以你不能直接对堆做二分查找——想找第 k 小，只能一个个 extractMin。

本质一句话：堆用"完全二叉树 + 堆序性质"以 O(1) 拿到最值，以 O(log n) 完成增删，是"只关心极值、不关心全序"场景的最优解。

二、插入：上浮（sift-up）

新元素先塞到数组末尾（保持完全二叉树形状），然后不断与父比较、若更小就交换，一路"浮"到该在的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MinHeap {
    private int[] a = new int[16];
    private int n = 0;

    void insert(int x){
        if (n == a.length) resize(2 * a.length);
        a[n] = x;
        siftUp(n++);
    }
    private void siftUp(int i){
        while (i > 0) {
            int p = (i - 1) / 2;
            if (a[i] >= a[p]) break;   // 堆序已满足
            swap(i, p);
            i = p;
        }
    }
    int peek(){ return a[0]; }
    private void swap(int i, int j){ int t = a[i]; a[i] = a[j]; a[j] = t; }
    private void resize(int cap){ int[] b = new int[cap]; System.arraycopy(a,0,b,0,n); a = b; }
}

三、取最小：下沉（sift-down）

删堆顶时，用最后一个元素填到堆顶（维持形状），再让它与较小的孩子比较、若更大就下沉，直到堆序恢复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int extractMin(){
    int min = a[0];
    a[0] = a[--n];
    siftDown(0);
    return min;
}
private void siftDown(int i){
    while (2 * i + 1 < n) {
        int child = 2 * i + 1;
        if (child + 1 < n && a[child + 1] < a[child]) child++;  // 选更小的孩子
        if (a[i] <= a[child]) break;
        swap(i, child);
        i = child;
    }
}
下沉：堆顶 11 被 2 替换后逐层比较 2 5 7 11 → 2 比 5、7 都小 堆序恢复，停止

本质一句话（操作代价）：上浮/下沉最多走树高 O(log n)，所以 insert / extractMin 都是 O(log n)，peek 是 O(1)。

四、建堆：自底向上 O(n) 的惊喜

若从空堆逐个 insert n 个元素，总代价 O(n log n)。但有个更妙的 Floyd 建堆：从最后一个非叶子节点开始向前每个做 siftDown，数学上可证总代价仅为 O(n)——比逐个插入还快。

1
2
3
4
5
static void buildHeap(int[] a){
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
}
// siftDown 与上述同，只是作用在传入的 a 与有效长度 n 上

坑②：O(n) 建堆之所以反直觉，是因为越靠下的节点高度越小、参与下沉的次数越少，加权平均后恰好收敛到线性。这是堆排序比"插入 n 次"更优的根基。

五、Java 与 C++：直接用还是自己写？

绝大多数时候直接用标准库，别手搓：

1
2
3
4
5
// Java：最小堆需要反转比较器（默认是最大堆）
PriorityQueue<Integer> pq = new PriorityQueue<>();   // 最小堆
pq.add(5); pq.add(1); pq.add(3);
while (!pq.isEmpty()) System.out.print(pq.poll() + " ");
// 输出：1 3 5
维度 Java PriorityQueue C++ std::priority_queue
默认 最小堆（poll 出最小） 最大堆（top 出最大）
取极值 peek() / poll() top() / pop()
底层 动态数组（二叉堆） 默认 vector（二叉堆）
能否遍历内部 仅迭代，无序 仅 top，无序

坑③：优先队列不支持高效随机删除/查找，它只承诺"快速拿到极值"。需要"降低某个节点优先级"时（如 Dijkstra 里松弛成功），通常用"懒删除"——往堆里塞一个更小的新副本，旧副本出堆时跳过。

六、小结

  • 是什么：二叉堆 = 完全二叉树 + 堆序性质，数组紧凑存储，靠下标算父子。
  • 坑：堆不是有序数组（不能二分查找）；建堆 O(n) 优于逐个插入；优先队列不擅长随机删除。
  • 本质一句话：堆用极小的常数代价，把"取极值"压到 O(1)、"增删"压到 O(log n)，是优先调度、堆排序、Dijkstra 的底层引擎——当你只关心"最大/最小是谁"而不关心全序时，它就是首选。

带着三个问题读每一篇会更有收获：① 我要的是最值还是全序？前者选堆，后者选 BST。 ② 上浮还是下沉更省？插入用上浮，删顶用下沉。 ③ 为什么建堆能 O(n) 而不是 O(n log n)？