ai-blog

堆（Heap）

一种用数组存储的完全二叉树数据结构，父节点始终比子节点更"优先"（最大堆中父 ≥ 子，最小堆中父 ≤ 子）。支持 O(log n) 插入、O(log n) 删除堆顶、O(1) 查看极值，是优先队列的标准实现。

一句话定义

堆（Heap） 是一棵用数组存储的完全二叉树，满足堆序性质：每个父节点都比它的子节点更"优先"。"优先"的含义取决于堆的类型——最大堆中父节点的值 ≥ 子节点，最小堆中父节点的值 ≤ 子节点。

堆解决的核心问题是：如何在动态变化的数据集中，高效地取出当前的最大值或最小值？

排序后取极值是 O(n log n)，而堆可以做到插入 O(log n)、取极值 O(1)、删除极值 O(log n)。

核心结构：数组就是完全二叉树

堆不需要指针、不需要节点对象——一个数组就是一棵树。完全二叉树的性质保证了节点在数组中连续排列，没有空洞，父子关系可以直接用下标算出来：

text
parent(i) = (i - 1) >> 1    // 位运算等价于 Math.floor((i-1)/2)，比除法快
left(i)   = 2 * i + 1       // 左子节点：当前下标×2 再 +1
right(i)  = 2 * i + 2       // 右子节点：左子节点 +1

以最小堆 [1, 3, 2, 7, 5, 4, 6] 为例：

Mermaid

数组下标 [0, 1, 2, 3, 4, 5, 6] 直接映射到树的层序遍历。不需要额外存储结构信息——这是堆比 BST 更节省内存的原因之一。

最大堆 vs 最小堆：唯一的区别是比较方向。最大堆保证堆顶是最大值，最小堆保证堆顶是最小值。实现时只需要翻转比较函数，其他逻辑完全一致。

可视化：亲手操作一个最小堆

最小堆可视化

两个核心操作：上浮与下沉

堆的所有操作都建立在两个基本动作上：

上浮（Sift Up）——用于插入

新元素追加到数组末尾（树的最后一个位置），然后不断与父节点比较，如果比父节点更"优先"就交换，直到满足堆序或到达根节点。

javascript
siftUp(i) {
  while (i > 0) {
    const parent = (i - 1) >> 1;
    if (this.compare(this.data[i], this.data[parent]) >= 0) break;
    [this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];
    i = parent;
  }
}

最坏情况从叶子冒泡到根——路径长度等于树高 O(log n)。

下沉（Sift Down）——用于删除堆顶

取出堆顶元素后，把数组末尾元素放到堆顶，然后不断与子节点中更"优先"的那个比较，如果不如子节点就交换，直到满足堆序或到达叶子。

javascript
siftDown(i) {
  const n = this.data.length;
  while (2 * i + 1 < n) {
    let child = 2 * i + 1;
    if (child + 1 < n && this.compare(this.data[child + 1], this.data[child]) < 0) {
      child++;
    }
    if (this.compare(this.data[i], this.data[child]) <= 0) break;
    [this.data[i], this.data[child]] = [this.data[child], this.data[i]];
    i = child;
  }
}

同样是 O(log n)。

建堆：Floyd 算法为什么是 O(n)

把无序数组变成堆有两种方式：

逐个插入：对每个元素调用上浮，总复杂度 O(n log n)。

Floyd 建堆：从最后一个非叶节点开始，倒序对每个节点执行下沉。总复杂度 O(n)。

为什么更快？直觉解释：大部分节点在底层，下沉距离短。叶子节点（占总数一半）不需要下沉；倒数第二层最多下沉 1 步；只有根节点需要下沉 log n 步。数学上这是一个收敛级数，总和为 O(n)。

javascript
static from(arr, compare) {
  const heap = new MinHeap(compare);
  heap.data = [...arr];
  for (let i = (arr.length >> 1) - 1; i >= 0; i--) {
    heap.siftDown(i);
  }
  return heap;
}

典型应用场景

Top-K 问题：维护一个大小为 K 的小顶堆。遍历数据，比堆顶大就替换并下沉。结束后堆里就是最大的 K 个元素。时间 O(n log K)，空间 O(K)。

合并 K 个有序序列：最小堆维护 K 个序列的当前头部，每次取最小的弹出，再把该序列的下一个元素入堆。时间 O(N log K)，N 为总元素数。

数据流中位数：用一个最大堆存较小的一半，一个最小堆存较大的一半，保持两个堆大小差 ≤ 1。中位数就是堆顶或两个堆顶的平均值。每次插入 O(log n)。

任务调度 / Dijkstra 最短路：优先队列天然适合"每次取优先级最高的任务"的场景。OS 进程调度、定时器管理、图算法中的松弛操作都依赖堆。

前端视角

JavaScript 没有内置的 PriorityQueue 或 Heap 类——需要手写或引用第三方库。

一个实际案例：React Scheduler 的任务优先级队列就是最小堆。React 内部用它按 expirationTime 排序待执行的任务，确保高优先级更新（用户输入）先于低优先级更新（数据预取）执行。源码在 packages/scheduler/src/SchedulerMinHeap.js，不到 50 行，实现了 push、pop、peek、siftUp、siftDown 五个函数。

极简实现参考：

javascript
class MinHeap {
  constructor(compare = (a, b) => a - b) {
    this.data = [];
    this.compare = compare;
  }
  get size() { return this.data.length; }
  peek()     { return this.data[0]; }
  push(val)  { this.data.push(val); this.siftUp(this.data.length - 1); }
  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) { this.data[0] = last; this.siftDown(0); }
    return top;
  }
  siftUp(i) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compare(this.data[i], this.data[parent]) >= 0) break;
      [this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];
      i = parent;
    }
  }
  siftDown(i) {
    const n = this.data.length;
    while (2 * i + 1 < n) {
      let child = 2 * i + 1;
      if (child + 1 < n && this.compare(this.data[child + 1], this.data[child]) < 0) child++;
      if (this.compare(this.data[i], this.data[child]) <= 0) break;
      [this.data[i], this.data[child]] = [this.data[child], this.data[i]];
      i = child;
    }
  }
}

易混淆点

概念区别
堆（数据结构） vs 堆内存（Heap Memory）完全不同的概念。数据结构的堆是完全二叉树；堆内存是运行时动态分配的内存区域，名字相同但无关联
堆 vs 二叉搜索树（BST）堆只保证父子关系（父 ≥ 子或父 ≤ 子），不保证左右子树的顺序；BST 保证左 < 根 < 右。堆适合取极值，BST 适合搜索和有序遍历
堆 vs 排序数组排序数组取极值 O(1) 但插入 O(n)；堆取极值 O(1) 且插入 O(log n)，适合动态数据

复杂度速查

操作时间复杂度
插入（push）O(log n)
查看堆顶（peek）O(1)
删除堆顶（pop）O(log n)
建堆（Floyd）O(n)
堆排序O(n log n)
空间O(n)，原地，无额外指针

引用本术语的文章