算法实现：建堆与排序

基于通用算法套路 · 核于 2026-07

速查

• 核心套路：升序用大根堆——建大根堆（堆顶最大）→ 堆顶换末尾 → 堆规模减一 → 对新堆顶下沉恢复堆序，重复 n 次。
• 下标映射（0 基）：节点 i 的父 ⌊(i-1)/2⌋、左子 2i+1、右子 2i+2；最后一个非叶子节点 ⌊n/2⌋-1。
• 下沉（sift down）：节点与「较大的子节点」比较，若子更大则交换、继续下沉，直到叶子或满足堆序——单次 O(log n)。
• 建堆 O(n)（Floyd 自底向下）：从最后一个非叶子节点 ⌊n/2⌋-1 倒着往前，每个节点执行下沉；总调整次数求和为 O(n)（不是 O(n log n)）。
• 排序 O(n log n)：n 次循环，每次「交换 + 对堆顶下沉」，单次下沉 ≤ O(log n)。
• 原地 O(1)：堆区与有序区共用同一数组，swap(a[0], a[i]) 把最大值换到末尾后，a[i..n-1] 即有序区。
• 降序用小根堆：堆顶最小换到末尾，末尾最小即降序——方向与堆性质相反，是高频易错点。
• 代码骨架：heapify（建堆）+ siftDown（下沉）+ for i: swap + siftDown（排序）三段。

一、下标映射：完全二叉树压平到数组

堆排序把数组 a[0..n-1] 视为一棵完全二叉树（按层从左到右编号），下标关系（0 基）：

节点 i 的父节点:    parent(i) = ⌊(i-1) / 2⌋
节点 i 的左子节点:  left(i)   = 2i + 1
节点 i 的右子节点:  right(i)  = 2i + 2
最后一个非叶子节点: last = ⌊n / 2⌋ - 1

例如 n=7 时，last = ⌊7/2⌋-1 = 2，即下标 0、1、2 是有子节点的（非叶子），3~6 是叶子。这个 last 是建堆的起点——叶子节点天然满足堆序（没有子节点可比），只需从 last 倒着往前调整非叶子节点。

二、下沉（sift down）：恢复堆序的核心操作

下沉（也叫「向下调整」「percolate down」）：当一个节点可能破坏堆序时，让它与较大的子节点比较，若子更大则交换，继续往下，直到叶子或满足堆序。大根堆的下沉（用于升序排序）：

// 大根堆下沉：把 a[idx] 下沉到正确位置，堆的有效范围是 [0, len)
function siftDown(a, idx, len) {
  while (true) {
    let big = idx;                   // 假设当前节点最大
    const l = 2 * idx + 1, r = 2 * idx + 2;
    if (l < len && a[l] > a[big]) big = l;   // 左子更大
    if (r < len && a[r] > a[big]) big = r;   // 右子更大
    if (big === idx) break;          // 已满足大根堆，停
    [a[big], a[idx]] = [a[idx], a[big]];     // 交换
    idx = big;                       // 继续下沉
  }
}

• 为什么找「较大的子节点」交换：大根堆要求父 ≥ 子，若父比某个子小，必须把父换下去；换到哪边？换到「较大的子」那侧，保证交换后新父（原较大的子）仍 ≥ 另一个子，堆序得以维持。
• 复杂度：树高 O(log n)，下沉最多走到叶子，单次 O(log n)。

三、建堆：Floyd 自底向下，O(n)

建堆（heapify）用 Floyd 算法——从最后一个非叶子节点 ⌊n/2⌋-1 倒着往前，对每个节点执行下沉。直觉上「n/2 个节点各 O(log n)」像 O(n log n)，但实际是 O(n)。

// 建大根堆：从最后一个非叶子节点倒着往前下沉
function heapify(a) {
  const n = a.length;
  for (let i = (n >> 1) - 1; i >= 0; i--) {  // 从 ⌊n/2⌋-1 到 0
    siftDown(a, i, n);
  }
}

为什么是 O(n) 而不是 O(n log n)

关键观察：不同节点的下沉深度不同——靠近叶子的节点下沉很浅（高度小），只有靠近根的少数节点下沉到 O(log n)。精确求和：

高度为 h 的节点最多有 ⌈n / 2^(h+1)⌉ 个，每个下沉最多 h 步
总调整次数 ≤ Σ(h=0→log n)  h × ⌈n / 2^(h+1)⌉
           = (n/2) × Σ h / 2^h
           = (n/2) × 2      （因为 Σ h/2^h = 2）
           = O(n)

所以建堆是线性的。注意：建堆 O(n) 并不能让堆排序总体降到 O(n)——排序段的 n 次下沉仍是 O(n log n)，主导了总复杂度。

四、排序：n 次交换 + 下沉

建堆完成后，堆顶 a[0] 是最大值。接下来反复「换到末尾 + 下沉」：

function heapSort(a) {
  const n = a.length;
  // 1. 建大根堆
  for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(a, i, n);
  // 2. 排序：堆顶换末尾，堆规模减一，下沉恢复堆序
  for (let i = n - 1; i > 0; i--) {
    [a[0], a[i]] = [a[i], a[0]];   // 最大值换到 a[i]（有序区）
    siftDown(a, 0, i);             // 对 [0, i) 的新堆顶下沉，i 之后是有序区
  }
  return a;
}

执行轨迹（以 [4, 10, 3, 5, 1] 升序为例）：

建大根堆后: [10, 5, 3, 4, 1]    堆顶 10 最大
i=4: swap(a[0],a[4]) → [1,5,3,4 | 10]   下沉 [0,4) → [5,4,3,1 | 10]
i=3: swap(a[0],a[3]) → [1,4,3 | 5,10]   下沉 [0,3) → [4,1,3 | 5,10]
i=2: swap(a[0],a[2]) → [3,1 | 4,5,10]   下沉 [0,2) → [3,1 | 4,5,10]
i=1: swap(a[0],a[1]) → [1 | 3,4,5,10]
最终: [1, 3, 4, 5, 10]  升序 ✅

五、完整代码模板

把三段合起来，一个完整的升序堆排序：

function heapSort(a) {
  const n = a.length;
  const siftDown = (idx, len) => {
    while (true) {
      let big = idx;
      const l = 2 * idx + 1, r = 2 * idx + 2;
      if (l < len && a[l] > a[big]) big = l;
      if (r < len && a[r] > a[big]) big = r;
      if (big === idx) break;
      [a[big], a[idx]] = [a[idx], a[big]];
      idx = big;
    }
  };
  for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(i, n); // 建堆 O(n)
  for (let i = n - 1; i > 0; i--) {                        // 排序 O(n log n)
    [a[0], a[i]] = [a[i], a[0]];
    siftDown(0, i);
  }
  return a;
}

降序版：把 siftDown 里两个 > 改成 <（即建小根堆、下沉时找「较小的子」），其余不变——堆顶最小换到末尾，末尾最小即降序。

六、为什么是原地

堆排序的「堆区」和「有序区」共用同一个数组，划分线随排序推进而移动：

建堆后:  [堆区: 整个数组                    ]
i=n-1轮: [堆区: a[0..n-2]    | 有序区: a[n-1]]
i=n-2轮: [堆区: a[0..n-3]    | 有序区: a[n-2..n-1]]
...
完成:    [有序区: 整个数组（升序）          ]

swap(a[0], a[i]) 一句话同时完成「取出堆顶最大值」和「放到有序区末尾」两件事，不需要额外数组搬运——这就是 O(1) 额外空间的实现根源。对比归并排序要 O(n) 辅助数组做 merge，堆排序在空间上更省。

交互演示

• 堆排序可视化演示 —— 建堆与 n 次交换下沉的过程

下一步

掌握了算法实现后，下一步分析它的特性——O(n log n) 最坏保证如何优于快排、为何实际却比快排慢（缓存与常数）、不稳定的原因、Top-K 为何用堆更优，见特性分析：最坏保证与应用。