二叉堆把「完全二叉树」和「数组」两件武器叠在一起：完全树保证高度恒为 O(log n)，数组存储让父子跳转变成 O(1) 的下标运算，于是「反复取极值」这一高频需求被压到取堆顶 O(1)、插入删除 O(log n)。它是优先队列的事实标准实现。

它解决什么问题

设想一类场景：数据源源不断地到来，而你反复需要当前的最大值或最小值——任务调度取优先级最高者、定时器找最近到期者、排行榜维护前 K 名。用无序数组，取极值要 O(n) 扫一遍；用有序数组，取极值 O(1) 但每次插入要 O(n) 挪动元素腾位置；用平衡二叉搜索树，两头都是 O(log n)，但实现重、常数大，而且杀鸡用了牛刀——你根本不需要全序，只需要知道「谁是老大」。

堆精准命中这个缺口：只维护「父不弱于子」的偏序关系，放弃兄弟之间、跨子树之间的顺序承诺。约束越弱，维护越便宜。需要注意一个常见的以讹传讹：堆在概念上并不要求是完全二叉树（斐波那契堆、二项堆就不是），只是二叉堆选择用完全二叉树实现，而完全树又恰好能无损地拍平进数组——下面说的堆，默认指二叉堆。

核心原理

堆序性质：只管父子，不管全局

  • 大顶堆：任意节点的值不小于其孩子；
  • 小顶堆：任意节点的值不大于其孩子。

性质是递归定义的，因此整棵树的最大（小）值必然在堆顶，取堆顶是 O(1)。但也仅此而已：左右孩子谁大没有约定，同层之间没有约定，所以堆不是有序结构——对堆做一次层序遍历得到的序列没有单调性，想「搜一个任意值」只能 O(n) 扫描。认清「堆 = 偏序」是避免一切误用的前提。

完全二叉树与数组的天作之合

完全二叉树「每层填满、最后一层靠左连续」的形状，让它可以按层序直接写入数组，不留任何空洞。根存下标 0 时，下标换算全是位运算级别的算术：

  • 节点 i 的左孩子：2i + 1，右孩子：2i + 2；
  • 节点 i 的父节点：(i - 1) / 2（整数除法）。

没有指针字段，没有内存碎片，连续存储还缓存友好。树高恒为 ⌊log n⌋，这是完全树的形状白送的性质，堆所有操作 O(log n) 的底气也正源于此。

深入机制

siftUp 与 siftDown：维护堆序的两个原子动作

插入：新元素追加到数组末尾（完全树的下一个空位），然后与父节点比较，若破坏堆序则交换，一路向上，直到不弱于父节点或到达堆顶。这个过程叫上浮（siftUp），最多走树高那么远。

删除堆顶：直接把根删掉会在树顶留个洞，难以收拾。标准做法是用数组末尾元素覆盖堆顶、数组长度减一，再让这个「空降兵」与两个孩子中更强者比较交换，一路向下，直到不弱于两个孩子或成为叶子。这叫下沉（siftDown）。为什么选「更强」的孩子交换？因为换上去的那个必须同时压得住另一个孩子，否则交换后堆序仍被破坏。

void siftUp(int[] a, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (a[parent] >= a[i]) break;      // 大顶堆：父已不弱于子
        swap(a, parent, i);
        i = parent;
    }
}

void siftDown(int[] a, int n, int i) {
    while (2 * i + 1 < n) {                // 至少存在左孩子
        int best = 2 * i + 1;
        if (best + 1 < n && a[best + 1] > a[best]) best++;  // 选更强的孩子
        if (a[i] >= a[best]) break;
        swap(a, i, best);
        i = best;
    }
}

两个操作都沿单条路径移动，代价 O(log n)。

建堆为什么能做到 O(n)

把无序数组整理成堆有两条路线。直觉路线是逐个插入：n 次上浮，O(n log n)。更优的 Floyd 路线是自底向上批量下沉：叶子天然满足堆序，无需处理；从最后一个非叶节点（下标 n/2 - 1）开始，逆序对每个节点做 siftDown。直觉上这似乎也是 O(n log n)，但精确算账后答案是 O(n)，关键在于绝大多数节点离底部很近：

  • 高度为 h 的节点至多有 ⌈n / 2^(h+1)⌉ 个，每个最多下沉 h 层；
  • 总代价上界为 Σ h · n / 2^(h+1)（h 从 1 到 log n）；
  • 级数 Σ h / 2^h 收敛于常数 2，故总代价 ≤ n · 常数 = O(n)。

一句话版直觉：底部节点数量占大头但只需走一两步，顶部节点要走得远但数量屈指可数，移动总量被几何级数压住，与「逐个插入」时每个新节点都可能从底部一路浮到顶的处境完全不同。

堆排序：原地、O(n log n)、不稳定

流程只有两步：

  1. 用 Floyd 法把数组建成大顶堆，O(n)；
  2. 反复执行「堆顶与堆区末尾交换 → 堆区长度减一 → 对新堆顶做 siftDown」，每轮把当前最大值钉进最终位置，n-1 轮共 O(n log n)。

交换堆顶与末尾是个一石二鸟的设计：既「取出」了最大值，又让末尾元素自动补位到根，删除堆顶的前置动作就此免掉。总复杂度 O(n log n)、原地 O(1) 额外空间。但相等元素的相对次序可能被「堆顶-末尾」的远距离交换打乱，所以堆排序不稳定；且其访问模式局部性差，实践中通常跑不过快速排序，只在需要稳定最坏上界或额外空间受限时出场。

工程实践

  • 优先队列：Java 的 PriorityQueue 默认小顶堆，构造大顶堆传 PriorityQueue<>((a, b) -> Integer.compare(b, a))。切记不要写成 b - a，整数溢出会让比较结果出错，这是真实出现过的事故级 bug。
  • Top-K：维护容量为 K 的小顶堆，堆顶是当前候选中的「守门员」，新元素超过它则替换之，O(n log k) 时间、O(k) 空间，且天然适配流式数据。数据流求中位数则是「大顶堆存左半 + 小顶堆存右半」的对顶结构。
  • 定时器与延迟队列：以触发时间为键的小顶堆，堆顶即最近到期的任务，线程只需睡到堆顶时刻；Kafka 的 DelayedOperationPurgatory、大量 RPC 框架的超时管理都基于这一结构（配合时间轮分摊竞争）。
  • 修改任意元素优先级：普通堆不支持高效定位，方案有二——维护「元素 → 下标」的索引堆，或放任旧记录留在堆里、弹出时按版本号丢弃（懒惰删除）。

对比与权衡

操作 无序数组 有序数组 平衡 BST 二叉堆
取极值 O(n) O(1) O(log n) O(1)
插入 O(1) O(n) O(log n) O(log n)
删除极值 O(n) O(1) O(log n) O(log n)
查找任意值 O(n) O(log n) O(log n) O(n)
建堆/初始化 — O(n log n) O(n log n) O(n)

堆在「取极值 + 增删」组合上做到了综合最优，代价是放弃了任意查找与全序输出。Top-K 若要求线性时间则应改用快速选择（期望 O(n)），堆解法的胜场在数据流与增量场景。

面试视角

为什么自底向上建堆是 O(n) 而不是 O(n log n)？ 下沉的代价取决于节点高度而非深度：占节点总数约一半的叶子高度为 0，四分之一的节点高度为 1，逐层减半。按 Σ h·n/2^(h+1) 求和，级数收敛，总移动次数被 n 的常数倍封住。与之对照，逐个插入时每个元素都可能上浮全程，才是 O(n log n)。

Top-K 第 K 大为什么用小顶堆而不是大顶堆？ 小顶堆的堆顶是当前 K 个候选中最弱的门槛，新元素只需与它比一次就能决定去留；若用大顶堆，堆顶是全局最大值，无法回答「我是否属于前 K」。方向选反是最常见的实现错误。

堆排序为什么不稳定？ 「堆顶与堆区末尾交换」会把末尾元素隔空提到堆顶，再靠下沉落位，相等元素在数组中的原始相对顺序可能因此被颠倒，而排序过程没有任何机制保护和恢复这种顺序。

如何合并 K 个有序链表？ 把各链表的头节点放入容量 K 的小顶堆，每轮弹出最小节点接到结果尾部，并把该节点的后继补入堆中，总代价 O(N log K)，远优于两两顺序合并的 O(NK)。

小结

  • 堆是偏序结构：只承诺父与子的强弱关系，堆顶即极值，别指望它有序或支持快速任意查找。
  • 完全二叉树的形状给了它 O(log n) 的高度，数组存储给了它 O(1) 的下标寻路，两者叠加才有堆的全部价值。
  • siftUp 管插入、siftDown 管删顶与建堆；Floyd 建堆 O(n) 的本质是「多数节点路短、少数节点路长」的几何级数收敛。
  • 堆排序原地且最坏 O(n log n) 但不稳定；工程上堆的主场是优先队列、Top-K 与定时器，选型时牢记它换取效率的代价是放弃全序。