堆排序算法：从堆数据结构到排序的完整可视化指南

---

为什么要学堆排序？

想象一下：你需要一个永不变慢的排序算法——无论数据是有序的、逆序的、还是完全随机的。

这就是堆排序。

由 J.W.J. Williams 于 1964 年发明，堆排序实现了一个了不起的特性：在任何情况下都保证 O(n log n) 的性能。没有退化，没有意外。

但堆排序的价值远不止于排序。掌握它，你将解锁：

• 优先队列 — 任务调度器的核心
• 图算法 — Dijkstra、Prim 等经典算法
• Top-K 问题 — 在海量数据中高效筛选
• 实时系统 — 需要可预测性能的场景

堆排序的秘密武器？一个优美的数据结构——二叉堆。

让我们从零开始构建理解。

---

堆数据结构

堆的特别之处

堆是一种特殊的完全二叉树，它的特别之处在于：每个节点都与其子节点遵循特定的顺序规则。

数组的魔法

精妙之处在于：我们可以用简单的数组存储堆，通过索引计算来定位节点：

对于索引为 i 的节点（从 0 开始）：
├── 父节点：     ⌊(i - 1) / 2⌋
├── 左子节点：   2i + 1
└── 右子节点：   2i + 2

可视化示例： 数组 [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

              [16]          ← 索引 0（根节点）
             /    \
          [14]    [10]      ← 索引 1, 2
          /  \    /  \
        [8]  [7] [9] [3]    ← 索引 3, 4, 5, 6
        / \   |
      [2][4] [1]            ← 索引 7, 8, 9

不浪费空间，没有指针开销，纯粹的效率。

---

最大堆 vs 最小堆

堆有两种类型，由其排序规则决定。

最大堆：大的在上

每个父节点都**≥**其子节点：

A[parent(i)] ≥ A[i]

结果： 最大元素永远在根节点。

最小堆：小的在上

每个父节点都**≤**其子节点：

A[parent(i)] ≤ A[i]

结果： 最小元素永远在根节点。

💡 升序排序使用最大堆。 每次提取都移除当前最大值并放到末尾。

---

MAX-HEAPIFY：核心操作

在排序之前，我们需要理解基础操作：MAX-HEAPIFY。

问题场景

想象一个节点比它的某个子节点更小。堆的性质被破坏了！

MAX-HEAPIFY 通过让违规节点下沉到正确位置来修复这个问题。

算法思路

MAX-HEAPIFY(A, heap_size, i):
  1. 在节点 i、左子节点、右子节点中找最大的
  2. 如果最大的不是节点 i：
     a. 交换节点 i 和最大节点
     b. 在交换后的位置递归执行

代码实现

JavaScriptJavaPython

Loading...

动画演示

下面的可视化展示了 MAX-HEAPIFY 如何修复数组 [4, 14, 10, 8, 7, 9, 3, 2, 1]。

注意：只有根节点 (4) 违反了堆性质。下面的所有节点都已经是有效的最大堆。观察 4 如何”下沉”到正确位置：

逐步分解：

1. 比较： 4 vs 子节点 14 和 10 → 14 最大
2. 交换： 4 ↔ 14，节点下沉到位置 1
3. 比较： 4 vs 子节点 8 和 7 → 8 最大
4. 交换： 4 ↔ 8，节点下沉到位置 3
5. 比较： 4 vs 子节点 2 和 1 → 4 最大
6. 完成！ 堆性质恢复

下沉为什么有效（深度剖析）

一个自然的问题：“当我们下沉节点时，难道不会破坏其他地方吗？”

答案在于一个关键前提条件。

前提条件

MAX-HEAPIFY 假设两个子树都已经是有效的最大堆。

只有根节点可能位置不对。

为什么不会破坏其他部分

当我们与最大的子节点交换时：

1. 父节点位置变得有效 — 我们选择了最大的值
2. 未触及的子树保持有效 — 我们从未修改它
3. 被触及的子树维持前提条件 — 只有它的根可能违规，所以我们递归处理

交换前：              交换后：
    [4] ← 违规           [14] ← 现在有效！
   /   \                /   \
[14]   [10]           [4]   [10] ← 未触及
                       ↑
                 在这里递归

这种优雅的设计确保了每一步的正确性。

时间复杂度

O(log n) — 最多下沉到叶子节点，树的高度是 log n。

---

从零构建堆

现在是魔法时刻：将任意数组转换成有效的最大堆。

核心洞察

叶子节点天然就是有效的堆！ 单个元素本身就满足堆性质。

所以我们只需要修复非叶子节点——而且是自底向上进行。

算法步骤

BUILD-MAX-HEAP(A):
  FOR i FROM ⌊n/2⌋ - 1 DOWNTO 0:
      MAX-HEAPIFY(A, n, i)

为什么这样做有效

Q1: 为什么从 ⌊n/2⌋ - 1 开始？

索引 ⌊n/2⌋ 到 n-1 的节点都是叶子节点。

从 ⌊n/2⌋ - 1（最后一个非叶子节点）开始跳过了一半的数组——即时节省 50%！

n = 10 的数组：
索引:  0   1   2   3   4   5   6   7   8   9
       └───非叶子节点───┘   └─────叶子节点────┘
                               （已经有效！）

Q2: 为什么要逆序遍历？

这是正确性的关键！

逆序： 处理节点 i 时，它的子节点（在 2i+1 和 2i+2）索引更大，所以已经被处理过了。前提条件满足！✅

正序： 处理节点 i 时，它的子节点还没被处理。前提条件失败！❌

Q3: 为什么结果保证正确？

循环不变式： 处理完索引 i 后，所有索引 ≥ i 的节点都是其子树的有效最大堆根。

归纳证明：

• 基础情况： 叶子节点天然有效
• 归纳步骤： 处理 i 时，两个子节点都是有效堆，所以 MAX-HEAPIFY 产生以 i 为根的有效堆
• 终止条件： 处理完索引 0 后，整个数组就是一个有效的最大堆

代码实现

JavaScriptJavaPython

Loading...

令人惊讶的复杂度：为什么是 O(n) 而不是 O(n log n)？

乍一看，你可能会想：“n/2 个节点 × 每个 O(log n) = O(n log n)”

但实际复杂度是 O(n)！🎉

这是算法分析中最优雅的结论之一。让我们来证明它。

粗略分析（错误）

粗略的分析假设：

• 我们对 n/2 个非叶子节点调用 MAX-HEAPIFY
• 每次调用花费 O(log n)（树的高度）
• 总计 = $\frac{n}{2} \times O(\log n) = O(n \log n)$ ❌

但这高估了，因为不是所有节点的下沉距离都相同！

精确分析（正确）

关键洞察：越靠近底部的节点，下沉距离越短。

在一个高度为 $h = \lfloor \log_2 n \rfloor$ 的完全二叉树中：

层级（从底部算起）	节点数量	最大下沉距离
0（叶子节点）	≤ n/2	0（跳过！）
1	≤ n/4	1
2	≤ n/8	2
k	≤ n/2^(k+1)	k
h（根节点）	1	h

数学证明

总工作量 = 对所有层级求和（第 $k$ 层节点数）×（最大下沉距离 $k$）：

$$T(n) = \sum_{k=0}^{h} \left\lceil \frac{n}{2^{k+1}} \right\rceil \cdot k \leq \sum_{k=0}^{h} \frac{n}{2^{k+1}} \cdot k = \frac{n}{2} \sum_{k=0}^{h} \frac{k}{2^k}$$

无穷级数 $\sum_{k=0}^{\infty} \frac{k}{2^k}$ 收敛于 2：

$$\sum_{k=0}^{\infty} \frac{k}{2^k} = \frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \frac{4}{16} + \cdots = 2$$

因此：

$$T(n) \leq \frac{n}{2} \times 2 = n = O(n)$$

直观理解

                    [1]           ← 1 个节点，最多下沉 h 层
                   /   \
                 [2]   [3]        ← 2 个节点，最多下沉 h-1 层  
                / \    / \
              [4] [5] [6] [7]     ← 4 个节点，最多下沉 h-2 层
              /\  /\  /\  /\
            [... n/4 个节点 ...]   ← 最多下沉 1 层
            [... n/2 个叶子 ...]  ← 0 工作量（跳过！）

底部密集的结构帮了我们：

• 一半的节点是叶子 → 0 工作量
• 四分之一的节点最多下沉 1 层 → $\frac{n}{4}$ 工作量
• 只有 1 个节点（根）下沉 $\log n$ 层 → $\log n$ 工作量

大部分工作都在底部节点上，而它们的高度很小！

---

排序算法

有了 BUILD-MAX-HEAP 和 MAX-HEAPIFY，排序算法简洁优美。

两阶段策略

HEAPSORT(A):
  // 阶段1: 将数组转换为最大堆
  BUILD-MAX-HEAP(A)
  
  // 阶段2: 反复提取最大值
  FOR i FROM n-1 DOWNTO 1:
      SWAP A[0] and A[i]      // 最大值放入已排序区域
      MAX-HEAPIFY(A, i, 0)    // 恢复剩余部分的堆性质

工作原理

1. 构建堆 — 最大元素升到根节点
2. 交换根节点和最后元素 — 最大值移到最终位置
3. 缩小堆 — 已排序元素不参与后续操作
4. 重新堆化 — 恢复剩余元素的堆性质
5. 重复 — 直到只剩一个元素

已排序的数组从右向左浮现！

---

交互式可视化

观看堆排序实况。见证两个阶段的展开：

1. 从无序数组构建最大堆
2. 提取最大值得到排序结果

切换树形视图和数组视图来理解堆结构如何映射到数组索引。

---

完整代码实现

三种语言的完整堆排序算法：

JavaScriptJavaPython

Loading...

---

性能分析

时间复杂度分解

操作	复杂度	说明
BUILD-MAX-HEAP	O(n)	虽然看起来不像，但确实是线性的
单次 MAX-HEAPIFY	O(log n)	树的高度
提取循环	O(n log n)	n-1 次提取 × 每次 O(log n)
总计	O(n log n)	比较排序的渐近最优

空间复杂度

O(1) — 堆排序是原地算法。只需要常数个额外变量。

与其他算法对比

算法	最好	平均	最坏	空间	稳定？
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	❌
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	❌
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	✅
插入排序	O(n)	O(n²)	O(n²)	O(1)	✅

关键洞察： 堆排序的最坏情况等于最好情况。永不退化。

---

练习题目

堆能够优雅地解决许多经典问题。这里是两道必备题目：

题目一：合并 K 个升序链表 (LC 23)

问题： 将 k 个有序链表合并成一个有序链表。

思路： 使用最小堆追踪所有 k 个链表头的最小元素。弹出、追加、前进。重复。

指标	数值
时间	O(N log k)，N = 总节点数
空间	O(k)

JavaPythonJavaScript

Loading...

题目二：数组中的第 K 个最大元素 (LC 215)

问题： 在未排序数组中找到第 k 大的元素。

方法：手写小顶堆

我们不使用内置的 PriorityQueue 或 heapq，而是从零开始实现堆 — 完美实践上面学到的概念！

核心思路： 维护一个大小为 k 的小顶堆。处理每个元素时：

• 如果堆大小 < k：直接插入
• 如果元素 > 堆顶：替换堆顶（k 个最大元素中的最小值）

处理完所有元素后，堆顶就是第 k 大的元素！

指标	数值
时间	O(n log k)
空间	O(k)

JavaPythonJavaScript

Loading...

上浮与下沉操作演示

下面的可视化演示了堆的两个核心操作：

上浮 (Sift Up ↑) — 插入新元素时：

1. 将元素添加到堆的末尾
2. 与父节点比较；如果更小（小顶堆），则交换
3. 重复直到恢复堆性质

下沉 (Sift Down ↓) — 替换根节点时：

1. 用新元素替换根节点
2. 与子节点比较；与更小的子节点交换
3. 重复直到恢复堆性质

---

延伸阅读

---

核心要点

何时选择堆排序

✅ 优势	❌ 权衡
保证 O(n log n) — 没有最坏情况意外	不稳定 — 相等元素可能重排
O(1) 空间 — 真正的原地排序	缓存不友好 — 内存访问分散
无栈溢出风险 — 有界递归	常数因子较大 — 通常输给优化后的快排

实际应用

除了排序，掌握堆还能解锁：

• 优先队列 — 标准实现使用堆
• Top-K 问题 — 高效找出最大/最小的 k 个元素
• 操作系统调度器 — 进程优先级管理
• 图算法 — Dijkstra 最短路径、Prim 最小生成树
• 外部排序 — 有序文件的多路归并

核心总结

💡 堆排序用原始速度换取可靠性。 当你需要有保证的性能——而不仅仅是平均情况性能——堆排序就是你的选择。理解堆还能打开通往优先队列、图算法等更多领域的大门。

掌握堆，它是计算机科学中最通用的数据结构之一。