堆与优先队列

讲解

堆（这里专指二叉堆）是一棵「近似完全」的二叉树，用数组紧凑存放：下标 i 的左右孩子分别是 2i+1 和 2i+2，父亲是 (i-1)>>1。它只维护一条偏序：每个节点都不大于（小顶堆）或不小于（大顶堆）它的孩子。注意堆不是有序结构——左右子树之间没有大小关系，它只保证一件事：堆顶永远是全局最值。插入和删除都是 O(log n)（沿一条树高路径调整），取最值 O(1)。

两个核心操作的手法。上浮（siftUp）：新元素放数组末尾，然后和父亲比，违反堆序就交换，一路冒到顶或停住。下沉（siftDown）：取堆顶时把末尾元素补到根部，然后和两个孩子的较小者比，该换就换，一路沉到底。掌握这两个原语，堆就没有秘密了。JS 没有内置堆，手写 MinHeap 是必备技能——好在代码不到 30 行。

堆的招牌应用是 Top K 问题。求第 K 大元素：维护一个容量 K 的小顶堆，扫完全部元素后堆顶即第 K 大——小顶堆像个「筛子」，比第 K 大还小的元素进不来。这个「容量 K 的反向堆」套路（求最大 K 个用小顶堆、求最小 K 个用大顶堆）初看反直觉，想清楚「堆里要保住的是谁」就通了。Top K 高频元素则先哈希计数，再把 (频次, 值) 丢进容量 K 的堆，把上一章的哈希表和本章的堆串了起来。

示例

手写一个支持自定义比较器的 MinHeap，再用它解决数组第 K 大元素和 Top K 高频元素：

import assert from 'node:assert/strict';

class MinHeap {
  constructor(cmp = (a, b) => a - b) {
    this.data = [];
    this.cmp = cmp;
  }
  size() {
    return this.data.length;
  }
  peek() {
    return this.data[0];
  }
  push(x) {
    this.data.push(x);
    let i = this.data.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.cmp(this.data[parent], this.data[i]) <= 0) break; // 堆序满足
      [this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
      i = parent;
    }
  }
  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1;
        const r = 2 * i + 2;
        let smallest = i;
        if (l < this.data.length && this.cmp(this.data[l], this.data[smallest]) < 0) smallest = l;
        if (r < this.data.length && this.cmp(this.data[r], this.data[smallest]) < 0) smallest = r;
        if (smallest === i) break;
        [this.data[smallest], this.data[i]] = [this.data[i], this.data[smallest]];
        i = smallest;
      }
    }
    return top;
  }
}

// 第 K 大：容量 K 的小顶堆，堆里留下的就是最大的 K 个
function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const x of nums) {
    heap.push(x);
    if (heap.size() > k) heap.pop(); // 弹掉最小的，保住大者
  }
  return heap.peek();
}

// Top K 高频：先计数，再按频次入堆
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);
  const heap = new MinHeap((a, b) => a.count - b.count);
  for (const [val, count] of freq) {
    heap.push({ val, count });
    if (heap.size() > k) heap.pop();
  }
  return heap.data.map((e) => e.val);
}

// 堆本身的行为：push 任意序，pop 出升序流
const heap = new MinHeap();
for (const x of [5, 1, 8, 3, 9, 2]) heap.push(x);
const sortedOut = [];
while (heap.size() > 0) sortedOut.push(heap.pop());
assert.deepStrictEqual(sortedOut, [1, 2, 3, 5, 8, 9]);

assert.strictEqual(findKthLargest([3, 2, 1, 5, 6, 4], 2), 5);
assert.strictEqual(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4), 4);

const top2 = topKFrequent([1, 1, 1, 2, 2, 3], 2);
assert.strictEqual(top2.length, 2);
assert.ok(top2.includes(1) && top2.includes(2));

console.log('堆示例全部通过');

「push 任意序、pop 出升序流」这个性质顺便给了一个排序算法：堆排序（全部 push 再逐个 pop，O(n log n)）——示例第一段其实就演示了它。

常见坑

• 求第 K 大用大顶堆：大顶堆容量 K 留下的是最小的 K 个，答案反了；记住「求大用小顶，求小用大顶」这个反向直觉。
• 孩子下标算错：0 基数组孩子是 2i+1 / 2i+2、父亲 (i-1)>>1；有些教材用 1 基（孩子 2i / 2i+1），别混。
• 下沉时只和左孩子比：必须和两个孩子中的较小者交换，否则换完仍可能违反堆序。
• pop 空堆或 peek 空堆：面试实现里先答边界——size 为 0 时的返回值要先定义清楚。
• 能用排序解决却强上堆：K 固定且数组小时直接排序更简洁；堆的价值在 K << n 或数据流式到达的场景，说清楚取舍。

小结

堆 = 数组紧凑存放的偏序树，堆顶即最值；上浮下沉两个原语搞定插入删除；Top K 用容量 K 的反向堆。下一章进入枚举的艺术：回溯。