高级数据结构

二叉堆与优先级队列

用数组装一棵完全二叉树

堆的巧妙之处在于它不需要指针。因为完全二叉树的形状是确定的， 节点位置可以直接算：

const parent = (i) => (i - 1) >> 1;
const left   = (i) => 2 * i + 1;
const right  = (i) => 2 * i + 2;
数组  [1, 3, 2, 7, 5, 4]
              1(0)
            /      \
         3(1)      2(2)
        /    \     /
     7(3)  5(4) 4(5)

⭐ 省掉指针不只是省内存 —— 数组连续存放，缓存命中率远高于链式的树， 这是堆在实践中很快的一个重要原因。

堆序：只管父子，不管兄弟

小顶堆的约束只有一条：每个节点都 ≤ 它的两个孩子。

🚨 注意兄弟之间没有任何顺序要求。上面例子里 3 和 2 谁大谁小都行。 这个约束比 BST 的「中序有序」弱得多 —— 弱约束换来的好处是：维护成本低（O(log n)），而拿最小值是 O(1)（就是根）。

⚠️ 所以堆不能用来做「查找某个值」或者「按序遍历」。 想同时要有序和快速取最值，那是别的结构（平衡树）的事。

上浮与下沉

只有两个操作，所有堆的功能都由它们拼出来。

class MinHeap {
  constructor(arr = []) { this.a = arr; this.heapify(); }
  get size() { return this.a.length; }
  peek() { return this.a[0]; }

  // 上浮：新元素放末尾，一路和父亲比，比父亲小就换上去
  _siftUp(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.a[p] <= this.a[i]) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }

  // 下沉：和两个孩子里较小的比，比它大就换下去
  _siftDown(i) {
    const n = this.a.length;
    for (;;) {
      const l = 2 * i + 1, r = l + 1;
      let m = i;
      if (l < n && this.a[l] < this.a[m]) m = l;
      if (r < n && this.a[r] < this.a[m]) m = r;   // 🚨 和 m 比，不是和 i 比
      if (m === i) break;
      [this.a[m], this.a[i]] = [this.a[i], this.a[m]];
      i = m;
    }
  }

  push(x) { this.a.push(x); this._siftUp(this.a.length - 1); }

  pop() {
    const top = this.a[0];
    const last = this.a.pop();
    if (this.a.length > 0) { this.a[0] = last; this._siftDown(0); }
    return top;
  }

  // ⭐ 自底向上建堆，见下
  heapify() {
    for (let i = (this.a.length >> 1) - 1; i >= 0; i--) this._siftDown(i);
  }
}

🚨 _siftDown 里第二个比较必须是 this.a[r] < this.a[m]，不能写成 < this.a[i]。 写错的话，左右孩子都比父亲小时，可能选中较大的那个换上去 —— 换完之后堆序仍然被破坏。

⚠️ 这个错的触发率跟规模强相关，而且是单调上升的。 每档跑 20000 组随机数组，判据是「heapify 之后不是合法堆，或者 pop 出来不是升序」：

n         1      2      3      4      5      6      7      8     10     20
暴露率   0.0%   0.0%  15.8%  49.1%  75.5%  92.2%  96.6%  99.8%  100%   100%

⭐ 真正测不出来的只有 n ≤ 2（元素太少，根本没有「两个孩子都比父亲小」的局面）。 n = 3 就已经有 15.8% 的概率暴露，n = 4 接近一半。

📌 所以拿三五个元素手工验证「堆看起来是对的」确实说明不了问题 —— 不是因为它测不出来，而是因为单次试验的成功不能证明什么： n = 5 时你有 24.5% 的概率恰好看到一个正确的结果。 👉 n = 8 就已经 99.8%，一组八元素的随机数据足以把这类错逼出来。

🚨 pop() 里的 if (this.a.length > 0) 同样不能省，理由见 Dijkstra 那篇：省掉之后单元素堆会把元素复活， size 归不了零，循环停不下来。

⭐ 建堆：O(n)，不是 O(n log n)

给一个乱序数组，把它变成堆。两种做法：

// 做法 A：逐个 push          O(n log n)
for (const x of arr) heap.push(x);

// 做法 B：自底向上 siftDown   O(n)
for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(i);

做法 B 更快，而且不是常数级的差别。

为什么：siftDown 的代价正比于节点到底部的距离。 而完全二叉树里，一半的节点是叶子（距离 0），四分之一距离 1，八分之一距离 2……

总代价 = n/2 × 0 + n/4 × 1 + n/8 × 2 + n/16 × 3 + … = n × Σ(k / 2^(k+1)) ≈ n

那个级数收敛到 1，所以总代价是 O(n)。

反观做法 A，siftUp 的代价正比于节点到顶部的距离， 而大部分节点离顶部很远 —— 于是最坏是 O(n log n)。

📌 一句话记法：「大部分节点在底层」——所以往下沉便宜，往上浮贵。

⚠️ 但这个差距在随机数据上几乎看不出来

理论归理论。n = 20000 实测交换次数（不看耗时 —— 交换次数不受机器和 JIT 影响）：

输入            heapify         逐个 push       倍数
随机        14700 ~ 15050    24400 ~ 26000     1.7×     ← 只能给区间
降序（最坏）        19991           247248    12.4×     （n log n ≈ 285754）
升序（最好）            0                0        —     ← push 一次都不用浮

⚠️ 随机那一行只能写区间，因为它依赖随机种子。 上面的区间来自 5 种取值分布 × 15 个种子；具体数字每次都不一样， 但倍数稳定在 1.7。降序那一行是确定性的，19991 / 247248 每次一模一样。

⭐ 随机数据上只差 1.7 倍，因为 siftUp 通常第一次比较就停了 —— 随机来的新元素大概率比它父亲大，压根不用上浮。O(n log n) 是最坏复杂度， 不是平均。升序输入更极端：新元素永远比父亲大，交换 0 次。

而降序输入（小顶堆的最坏情况）每个新元素都要一路浮到根， push 版的交换次数直奔 n log n，heapify 仍稳在 n 附近。

⭐ 「heapify 是 O(n)」最干净的证据是规模翻倍交换次数怎么涨：

n =  20,000    交换  14859             c/n = 0.743
n =  40,000    交换  29814    ×2.01    c/n = 0.745
n =  80,000    交换  59651    ×2.00    c/n = 0.746
n = 160,000    交换 119018    ×2.00    c/n = 0.744

👉 每个元素平均只交换 0.744 次，而且这个比值一动不动 —— 这就是 O(n)。

📌 这也是为什么「用哪个建堆」在算法题里往往无所谓， 但在可能被对手构造输入的场合（在线服务）必须用 heapify。

堆排序与 Top K

// 堆排序：建堆 O(n) + n 次 pop，每次 O(log n) → O(n log n)
function heapSort(arr) {
  const h = new MinHeap([...arr]);
  const res = [];
  while (h.size > 0) res.push(h.pop());
  return res;
}

⚠️ 堆排序不稳定（相等元素的相对顺序会变），而且实践中常常比快排慢 —— 它的访问模式跳来跳去，缓存不友好。它的价值在于最坏也是 O(n log n) （快排最坏 O(n²)），以及原地版本只要 O(1) 额外空间。

Top K 才是堆真正的主场：

// 求最大的 k 个：维护一个大小为 k 的【小顶堆】
function topK(nums, k) {
  const h = new MinHeap([]);
  for (const x of nums) {
    h.push(x);
    if (h.size > k) h.pop();      // 弹掉最小的，堆里始终是当前最大的 k 个
  }
  return h.a;
}

🚨 求最大的 k 个要用小顶堆，这个反直觉的点几乎每次都有人搞反。 道理是：堆顶是「当前 k 个里最差的那个」，来了新元素只要跟它比 —— 比它还差就直接扔，比它好就换掉它。

⭐ 复杂度 O(n log k)，而排序是 O(n log n)。k 远小于 n 时差距很大； 更重要的是它只占 O(k) 内存，所以能处理装不进内存的数据流。

下一步

堆用「弱约束」换到了 O(1) 取最值。 字典树走的是另一条路 —— 用空间换时间，把公共前缀合并起来。

练习

勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。