排序算法系列 08：堆排序——用数据结构的力量排序

堆排序是三个 O(n log n) 比较排序里最"硬核"的一个。归并靠分治，快排靠分区，堆排靠的是一个叫"堆"的数据结构。

理解堆排序的关键不是排序本身，而是先搞明白堆是什么、怎么维护。搞定这个，排序就是水到渠成的事。

先说堆

堆本质上是一棵完全二叉树，满足一个性质：

• 大顶堆：每个父节点 ≥ 它的子节点（堆顶是最大值）
• 小顶堆：每个父节点 ≤ 它的子节点（堆顶是最小值）

排序用的是大顶堆。堆顶永远是当前最大值——这就是堆排序的核心武器。

堆虽然逻辑上是树，但存储用的是数组。对于下标 i：

左子节点：2 * i + 1
右子节点：2 * i + 2
父节点：Math.floor((i - 1) / 2)

比如数组 [9, 7, 5, 1, 2] 对应的树长这样：

        9
      /   \
     7     5
    / \
   1   2

父节点都 ≥ 子节点，大顶堆没问题。

核心思想

第一步，把数组建成大顶堆——堆顶就是最大值。

第二步，把堆顶和数组最后一个元素交换，然后"堆的范围"缩小一位（最大值已经到了正确位置），再重新调整堆。

重复第二步，每次都把当前最大值放到末尾，数组就从后往前逐渐变成升序。

你可以这么理解：堆排序就是不断问"当前最大的是谁"，然后把它请到后面去。

关键操作：heapify（下沉调整）

堆排序最核心的函数是 heapify——当某个节点的值比子节点小时，把它往下沉，直到堆性质恢复。

过程：

1. 比较当前节点和它的左右子节点
2. 如果子节点更大，跟最大的那个交换
3. 交换后继续往下检查，直到不需要再交换

代码实现

function heapSort(arr) {
  const result = [...arr];
  const n = result.length;

  // 第一步：建大顶堆（从最后一个非叶子节点开始）
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(result, n, i);
  }

  // 第二步：不断取堆顶放到末尾
  for (let end = n - 1; end > 0; end--) {
    [result[0], result[end]] = [result[end], result[0]];
    heapify(result, end, 0);
  }

  return result;
}

function heapify(arr, heapSize, rootIndex) {
  let largest = rootIndex;
  const left = 2 * rootIndex + 1;
  const right = 2 * rootIndex + 2;

  if (left < heapSize && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < heapSize && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest !== rootIndex) {
    [arr[rootIndex], arr[largest]] = [arr[largest], arr[rootIndex]];
    heapify(arr, heapSize, largest);
  }
}

console.log(heapSort([5, 2, 9, 1, 7]));
// [1, 2, 5, 7, 9]

两个阶段的代码都很短。难点在于理解 heapify 的递归下沉过程。

为什么建堆从 n/2 - 1 开始？

数组后半段全是叶子节点——没有子节点，天然满足堆性质，不需要调整。

最后一个有子节点的位置是 Math.floor(n / 2) - 1，从这里往前逐个做 heapify 就能把整个数组调整成大顶堆。

建堆的时间复杂度其实是 O(n)，不是 O(n log n)——因为越靠近底部的节点下沉距离越短，而底部的节点最多。

复杂度

和归并一样，堆排序的时间复杂度永远是 O(n log n)，不会退化。

空间复杂度 O(1)——原地排序，不需要额外数组。这比归并排序强。

稳定性：不稳定。堆调整和交换会打乱相等元素的相对顺序。

堆排序 vs 快排 vs 归并

堆排序在纸面上很完美——时间稳定、空间最小。但实际跑起来通常比快排慢，原因是堆的访问模式对 CPU 缓存不友好：父节点和子节点在数组里的位置跳跃性很大，缓存命中率低。

所以堆排序的实际定位是：当你需要严格 O(n log n) 的时间上界，又不能多用空间时，它是最佳选择。 比如 Introsort 在快排递归太深时就会切到堆排。

堆的思想不止用在排序

学堆排序的附加收益很大。堆这个数据结构在别的地方用得更多：

• 优先队列：每次取最大/最小值，O(log n)
• Top K 问题：找前 K 大/小元素
• 任务调度：按优先级出队
• Dijkstra 最短路：用小顶堆优化

所以堆排序不只是学一个排序，更是打开堆这个数据结构大门的钥匙。

下一篇切换赛道，来看非比较排序的第一个代表：计数排序——不比大小，照样能排序。

系列导航

上一篇：排序算法系列 07：快速排序——面试必问，工程必用

下一篇：排序算法系列 09：计数排序——不比较，直接数