堆排序（Heap Sort）
数据结构与算法专题 · 基于堆的选择排序
专题：数据结构与算法系统学习
关键词：数据结构, 算法, 堆排序, Heap Sort, 建堆, heapify, 下滤, 原地排序, 选择排序
一、堆排序概述
堆排序（Heap Sort）是一种基于二叉堆（Binary Heap）数据结构的比较排序算法。它由 J. W. J. Williams 于 1964 年发明，随后由 Robert W. Floyd 在同年优化了建堆过程。堆排序可以被视为一种改进的选择排序——传统选择排序每次需要 O(n) 时间找到最大元素，而堆排序利用堆这种数据结构将这一操作优化到 O(log n)，从而将整体时间复杂度从 O(n^2) 降低到 O(n log n)。
堆排序的核心思想是：首先将待排序数组构建成一个最大堆（Max Heap），此时堆顶元素就是整个数组的最大值；然后将堆顶元素与数组末尾元素交换，将最大值放到正确的位置；接着对剩余 n-1 个元素重新调整成最大堆，再次取出堆顶的最大值。如此重复，直到所有元素有序。由于堆排序在排序过程中始终只使用常数额外空间，它属于原地排序（In-place Sorting）算法。
堆排序具有以下显著特征：最好、最坏、平均时间复杂度均为 O(n log n)；空间复杂度为 O(1)（原地排序）；但堆排序不是稳定排序算法。在工程实践中，堆排序常用于优先级队列的实现，以及需要在 O(n log n) 时间完成排序但无法承受快速排序最坏情况 O(n^2) 的场景。
二、堆数据结构
堆（Heap）是一种特殊的完全二叉树（Complete Binary Tree）。如果一棵深度为 h 的二叉树，除了第 h 层外，其他各层都被完全填满，并且第 h 层的所有节点都尽可能地靠左排列，那么这棵树就是一棵完全二叉树。堆正是基于这种结构定义的。
2.1 最大堆与最小堆
- 最大堆（Max Heap）：每个父节点的值都大于或等于其子节点的值。即对于任意节点 i，满足
arr[i] >= arr[2i+1] 且 arr[i] >= arr[2i+2]。最大堆的根节点存放的是整个堆中的最大值。
- 最小堆（Min Heap）：每个父节点的值都小于或等于其子节点的值。即对于任意节点 i，满足
arr[i] <= arr[2i+1] 且 arr[i] <= arr[2i+2]。最小堆的根节点存放的是整个堆中的最小值。
堆排序通常使用最大堆来实现升序排序，使用最小堆来实现降序排序。
2.2 堆的数组表示
由于堆是完全二叉树，我们可以使用数组来高效地存储堆。不使用数组的第一个元素（索引 0 留空）可以使子节点寻址公式更直观，但更常见的做法是使用基于 0 的索引。对于数组中索引为 i 的元素：
- 父节点索引：
parent(i) = (i - 1) // 2
- 左子节点索引：
left(i) = 2 * i + 1
- 右子节点索引：
right(i) = 2 * i + 2
示例：数组 [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] 对应的最大堆结构为：根节点 16，其左孩子 14（索引 1）、右孩子 10（索引 2）；14 的左孩子 8（索引 3）、右孩子 7（索引 4）；以此类推。
三、核心操作：heapify（下滤）
heapify（又称下滤、下沉、筛降）是堆排序中最核心的基本操作。它的作用是：当某个节点的值不满足堆的性质时，将其与子节点交换，使其"下沉"到正确的位置，直到以该节点为根的子树重新满足堆的性质。
3.1 heapify 的算法逻辑
给定一个数组 arr 和一个索引 i，假设以 left(i) 和 right(i) 为根的子树已经分别是合法的最大堆，但 arr[i] 可能小于其子节点。heapify 的过程如下：
- 在 arr[i]、arr[left(i)]、arr[right(i)] 三者中找到最大值
- 如果最大值不是 arr[i]，则将 arr[i] 与最大值所在的子节点交换
- 递归（或迭代）地对被交换的子节点执行 heapify
def heapify(arr, n, i):
# 初始化最大值为当前节点 i
largest = i
left = 2 * i + 1
right = 2 * i + 2
# 如果左子节点存在且大于当前最大值
if left < n and arr[left] > arr[largest]:
largest = left
# 如果右子节点存在且大于当前最大值
if right < n and arr[right] > arr[largest]:
largest = right
# 如果最大值不是当前节点，交换并继续向下调整
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
时间复杂度分析：heapify 的单次操作时间复杂度为 O(log n)，因为最坏情况下，一个节点需要从堆顶一直下沉到叶子节点，而堆的高度为 ⌊log₂n⌋。
迭代版本的 heapify：递归实现的 heapify 可能因递归深度导致栈溢出（虽然一般来说堆的深度只有 log n，风险较小）。下面提供了等价的迭代实现，使用 while 循环代替递归，更加安全高效。
def heapify_iterative(arr, n, i):
while True:
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest == i:
break
arr[i], arr[largest] = arr[largest], arr[i]
i = largest # 继续向下调整
四、建堆过程
建堆（Build Heap）是将一个无序数组构建成最大堆（或最小堆）的过程。建堆的核心思想是从最后一个非叶节点开始，自底向上地调用 heapify。
4.1 最后一个非叶节点
在完全二叉树中，最后一个非叶节点的索引为 n // 2 - 1（基于 0 索引）。这是因为最后一个元素的索引为 n-1，它的父节点即为最后一个非叶节点：parent(n-1) = (n-1 - 1) // 2 = n // 2 - 1。
4.2 建堆的代码实现
def build_max_heap(arr):
n = len(arr)
# 从最后一个非叶节点开始，自底向上 heapify
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
return arr
4.3 O(n) 建堆的时间复杂度证明
很多人直觉上认为建堆需要 O(n log n) 时间，但实际上建堆的时间复杂度是 O(n)。这是因为在自底向上的建堆过程中，高度越高的节点数量越少，而每个节点 heapify 的时间与其高度成正比。具体分析如下：
- 高度为 h 的节点最多有 ⌈n / 2^(h+1)⌉ 个
- 每个高度为 h 的节点的 heapify 操作最多需要 h 次交换（O(h) 时间）
- 总时间的上界为：∑_{h=0}^{log n} ⌈n / 2^(h+1)⌉ · O(h) = O(n · ∑_{h=0}^{∞} h / 2^h) = O(n)
其中无穷级数 ∑ h/2^h = 2 是一个收敛级数，因此总时间与 n 呈线性关系。这个分析结果意味着：在无序数组上构建堆只需要 O(n) 的时间，而非 O(n log n)。
直观理解：O(n) 建堆的关键在于，大部分节点都位于堆的底部（接近叶子节点），这些节点的 heapify 操作非常快（只需要很少的交换甚至不需要交换）。叶子节点本身不需要任何操作，倒数第二层的节点最多只需要 1 次交换，以此类推。将各层的工作量加总后，恰好是 O(n)。
五、排序过程详解
在建堆完成后，堆排序进入排序阶段。排序阶段的核心是一个循环：每次将堆顶元素（当前最大值）与堆的最后一个元素交换，然后对新的堆顶执行 heapify 恢复堆的性质，同时将堆的逻辑大小减一。
5.1 排序阶段算法流程
- 建堆：将无序数组构建成最大堆
- 交换：将堆顶元素 arr[0] 与当前堆的最后一个元素 arr[i] 交换
- 下滤：将堆的大小减一（排除已排好的最大值），对新的堆顶执行 heapify
- 重复步骤 2-3，直到堆的大小为 1
5.2 完整排序实现
def heap_sort(arr):
n = len(arr)
# 阶段一：建堆（O(n)）
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 阶段二：排序（O(n log n)）
for i in range(n - 1, 0, -1):
# 将堆顶元素（最大值）与当前堆的最后一个元素交换
arr[0], arr[i] = arr[i], arr[0]
# 对新的堆顶执行 heapify，堆的大小为 i
heapify(arr, i, 0)
return arr
5.3 排序过程演示
以数组 [4, 10, 3, 5, 1] 为例，演示堆排序的完整过程：
- 建堆后：[10, 5, 3, 4, 1]（最大堆）
- 第 1 轮：交换 arr[0]=10 与 arr[4]=1 → [1, 5, 3, 4, 10] → heapify 堆顶 → [5, 4, 3, 1, 10]
- 第 2 轮：交换 arr[0]=5 与 arr[3]=1 → [1, 4, 3, 5, 10] → heapify 堆顶 → [4, 1, 3, 5, 10]
- 第 3 轮：交换 arr[0]=4 与 arr[2]=3 → [3, 1, 4, 5, 10] → heapify 堆顶 → [3, 1, 4, 5, 10]（堆大小为 2，堆顶 3 > 1，满足）
- 第 4 轮：交换 arr[0]=3 与 arr[1]=1 → [1, 3, 4, 5, 10] → heapify 堆顶 → [1, 3, 4, 5, 10]（堆大小为 1，结束）
- 最终结果：[1, 3, 4, 5, 10]（升序排列）
注意：在排序阶段，每次 heapify 的参数 n 传递的是 i（当前堆的逻辑大小），而不是整个数组的长度。这是因为 arr[i:] 已经包含了已排序好的最大元素，不应再参与堆的调整。
六、Python 完整实现与测试
下面是一个完整的堆排序实现，包含辅助函数、主排序函数和测试代码：
def heapify(arr, n, i):
"""对以 i 为根节点的子树执行下滤操作（迭代版本）"""
while True:
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest == i:
break
arr[i], arr[largest] = arr[largest], arr[i]
i = largest
def heap_sort(arr):
"""堆排序主函数（原地排序）"""
n = len(arr)
# 建堆：从最后一个非叶节点开始自底向上调整
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 排序：依次取出堆顶最大值
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
# 测试
if __name__ == "__main__":
test_cases = [
[4, 10, 3, 5, 1],
[64, 34, 25, 12, 22, 11, 90],
[1, 2, 3, 4, 5], # 已有序
[5, 4, 3, 2, 1], # 逆序
[3, 3, 3, 3], # 全部相等
[42], # 单个元素
[], # 空数组
]
for case in test_cases:
original = case[:]
sorted_arr = heap_sort(case)
print(f"原始: {original} 排序后: {sorted_arr}")
运行上述测试代码的输出：
原始: [4, 10, 3, 5, 1] 排序后: [1, 3, 4, 5, 10]
原始: [64, 34, 25, 12, 22, 11, 90] 排序后: [11, 12, 22, 25, 34, 64, 90]
原始: [1, 2, 3, 4, 5] 排序后: [1, 2, 3, 4, 5]
原始: [5, 4, 3, 2, 1] 排序后: [1, 2, 3, 4, 5]
原始: [3, 3, 3, 3] 排序后: [3, 3, 3, 3]
原始: [42] 排序后: [42]
原始: [] 排序后: []
七、时间复杂度分析
堆排序的时间复杂度分析分为两个阶段：
7.1 建堆阶段：O(n)
如第四章所述，从最后一个非叶节点开始自底向上调用 heapify，总时间复杂度为 O(n)。这一结论可以通过级数求和严格证明，也可以从直观上理解：大部分节点位于堆的底层，它们需要的调整次数很少。
7.2 排序阶段：O(n log n)
在排序阶段，我们需要执行 n-1 次循环，每次循环做一次 O(1) 的交换操作和一次 O(log n) 的 heapify 操作。因此排序阶段的总时间复杂度为 O(n log n)。
7.3 总体复杂度
| 指标 | 复杂度 | 说明 |
|---|
| 最好情况 | O(n log n) | 即使数组已经有序，仍然需要建堆和排序 |
| 最坏情况 | O(n log n) | 堆排序没有"反转对"的敏感度，始终一致 |
| 平均情况 | O(n log n) | 数据分布不影响复杂度 |
| 空间复杂度 | O(1) | 原地排序，仅需常数额外空间 |
| 稳定性 | 不稳定 | 长距离交换破坏相对顺序 |
值得注意：虽然堆排序的渐进时间复杂度和归并排序一样是 O(n log n)，但堆排序在实际运行中通常比快速排序和归并排序慢（常数因子更大）。这是因为 heapify 操作中的比较次数较多，且 CPU 缓存局部性不如快速排序好——堆排序访问数组的方式是跳跃式的，而非连续的。
八、堆排序的不稳定性
堆排序是一个不稳定的排序算法。这意味着当数组中有相等元素时，排序后它们的相对顺序可能发生改变。
8.1 不稳定的原因
不稳定性的根本原因在于堆排序中存在长距离交换。在建堆和排序过程中，堆顶元素会与远处的元素交换，这种跨越多个位置的交换会破坏相等元素的原始相对顺序。具体来说：
- 在建堆阶段，heapify 可能将一个子节点提升到父节点的位置，从而改变相等元素的顺序
- 在排序阶段，堆顶元素与数组末尾元素的交换更是跨越了整个堆的范围
8.2 不稳定性示例
考虑数组 [5a, 8, 5b, 3]，其中 5a 和 5b 是两个值相等但不同的元素（下标 a 表示原始顺序中在前）。经过堆排序后，结果可能是 [3, 5b, 5a, 8]，5b 出现在了 5a 之前，相对顺序被改变了。
实际影响：在大多数只需要对数值进行排序的场景中，不稳定性并不重要。但如果需要根据多个键进行排序（例如先按年龄再按姓名），或者需要保留输入数据的原始顺序信息，则应优先选择稳定的排序算法（如归并排序或插入排序）。
九、堆排序 vs 快速排序 vs 归并排序
这三大 O(n log n) 排序算法各有优劣，下表对它们进行了全面对比：
| 比较维度 | 堆排序 | 快速排序 | 归并排序 |
|---|
| 最好时间复杂度 | O(n log n) | O(n log n) | O(n log n) |
| 最坏时间复杂度 | O(n log n) | O(n^2) | O(n log n) |
| 平均时间复杂度 | O(n log n) | O(n log n) | O(n log n) |
| 空间复杂度 | O(1) | O(log n)（递归栈） | O(n)（辅助数组） |
| 是否稳定 | 不稳定 | 不稳定 | 稳定 |
| 是否原地 | 是 | 是 | 否（需要 O(n) 辅助空间） |
| 缓存局部性 | 差 | 好 | 好 |
| 常数因子 | 大 | 小 | 中等 |
| 适合场景 | 嵌入式/内存受限 | 通用排序 | 外部排序/需要稳定 |
选择建议：
- 如果内存非常宝贵（嵌入式系统、微控制器）且需要 O(n log n) 保证 → 选堆排序
- 如果是一般应用场景且数据随机 → 选快速排序（实践中最快）
- 如果需要稳定排序或排序链表 → 选归并排序
- Python 和 Java 的默认排序使用 TimSort（归并排序的混合变体），而非纯归并排序
十、使用 Python heapq 模块实现堆排序
Python 标准库中的 heapq 模块提供了堆操作的支持。虽然从零实现堆排序是很好的学习方式，但在工程实践中，我们通常直接使用 heapq 来完成堆相关操作。heapq 默认实现的是最小堆。
10.1 使用 heapq 实现升序排序
import heapq
def heap_sort_heapq(arr):
"""使用 heapq 模块实现堆排序"""
# 建堆（最小堆）
heapq.heapify(arr)
# 依次弹出堆顶最小值
result = []
for _ in range(len(arr)):
result.append(heapq.heappop(arr))
return result
# 测试
data = [4, 10, 3, 5, 1]
print(heap_sort_heapq(data)) # 输出: [1, 3, 4, 5, 10]
需要注意的是，上述实现使用了额外的 O(n) 空间（result 列表），因为 heapq.heappop 会改变原数组的大小。如果要实现原地排序，可以先将所有元素压入堆中，然后从后向前填充结果。但更常用的做法是使用 heapq.nsmallest 和 heapq.nlargest 方法。
10.2 heapq 常用函数
| 函数 | 功能 | 时间复杂度 |
|---|
heapq.heapify(x) | 将列表 x 原地转换为最小堆 | O(n) |
heapq.heappush(heap, item) | 向堆中插入一个元素 | O(log n) |
heapq.heappop(heap) | 弹出并返回堆顶元素（最小值） | O(log n) |
heapq.heappushpop(heap, item) | 先插入再弹出，效率高于分别调用 | O(log n) |
heapq.nlargest(n, iterable) | 返回可迭代对象中最大的 n 个元素 | O(n log k) |
heapq.nsmallest(n, iterable) | 返回可迭代对象中最小的 n 个元素 | O(n log k) |
工程实践：当需要获取 Top-K 元素时（如"从 10 亿条日志中找出出现频率最高的 100 个"），使用 heapq.nlargest 或 heapq.nsmallest 是最佳实践。它们内部使用大小为 k 的堆，时间复杂度为 O(n log k)，空间复杂度为 O(k)，远优于全部排序的 O(n log n)。
十一、Floyd 建堆算法优化
Robert W. Floyd 在 1964 年对堆排序进行了重要优化，主要体现在建堆阶段。标准的建堆方法需要从最后一个非叶节点开始，对每个节点调用 heapify。Floyd 发现，对于叶子节点密集的底层区域，可以跳过大部分比较，从而减少建堆过程中的比较次数。
11.1 Floyd 建堆的核心思想
传统建堆方法对每个非叶节点调用标准的 heapify，需要与两个子节点分别比较。Floyd 提出了一种更高效的建堆方式：
- 下滤路径优先：不直接比较父节点与两个子节点，而是优先找到从根到叶子的"大值路径"
- 减少比较次数：Floyd 建堆利用已知的子堆已经是合法最大堆这一事实，直接沿着子节点中较大的那个下探，减少了不必要的比较
11.2 减少的常数因子
虽然 Floyd 建堆的理论时间复杂度仍然是 O(n)，但它将建堆过程中的比较次数从大约 2n 减少到了约 n 次。对于大型数据集，这种优化可以带来约 20-30% 的性能提升。在实际的 C++ STL 的 std::make_heap 和 Python heapq 的 heapify 实现中，都采用了 Floyd 提出的建堆策略。
def floyd_heapify(arr, n, i):
"""Floyd 优化的下滤——沿着较大子节点单向下探"""
while True:
child = 2 * i + 1 # 左子节点
if child >= n:
break
# 选择较大的子节点
if child + 1 < n and arr[child + 1] > arr[child]:
child += 1
# 如果父节点小于较大子节点，交换
if arr[i] < arr[child]:
arr[i], arr[child] = arr[child], arr[i]
i = child
else:
break
Floyd 建堆算法的优化本质上是常数优化而非渐进优化——它不改变 O(n) 的时间复杂度，但在实际运行中减少了比较和交换操作的次数。
十二、堆排序的原地性
堆排序是最优秀的原地排序（In-place Sorting）算法之一。所谓原地排序，指的是在排序过程中，除了输入数组本身所使用的空间外，只使用 O(1) 的额外空间。堆排序完美地满足这一要求。
12.1 为什么堆排序是原地排序
- 堆排序直接在输入数组上进行操作，不需要创建额外的辅助数组（与归并排序不同）
- 排序过程中只使用了几个局部变量（索引、临时交换变量），它们占用 O(1) 空间
- heapify 函数如果使用迭代实现，不会产生递归调用的栈开销；即使使用递归实现，栈深度也只有 O(log n)，但通常实现中都使用迭代版本，严格保证 O(1) 额外空间
12.2 原地排序的意义
实际价值：在内存受限的环境中（如嵌入式系统、实时操作系统、微控制器编程），原地排序的优势非常显著。当需要排序的数据量接近可用内存上限时，归并排序的 O(n) 辅助空间可能成为致命缺陷，而堆排序则不受影响。此外，在数据库内部排序、操作系统内核排序等底层场景中，原地排序也是首选。
在三大 O(n log n) 排序算法中，堆排序是唯一同时满足"最坏情况 O(n log n)"和"原地排序"两个条件的算法。快速排序虽然原地，但最坏情况会退化为 O(n^2)；归并排序虽然最坏情况稳定 O(n log n)，但需要 O(n) 辅助空间。堆排序在这一点上具有不可替代的优势。
十三、堆排序的变体与应用
13.1 弱堆排序
弱堆排序（Weak Heap Sort）是堆排序的一种变体，它使用弱堆（Weak Heap）代替标准的二叉堆。弱堆放宽了父子节点之间的大小关系约束，允许更高效的建堆过程。弱堆排序的比较次数约为 n log₂n - 0.9n，是理论上比较次数最接近信息论下界的排序算法之一。
13.2 平滑排序
平滑排序（Smooth Sort）是由 Edsger Dijkstra 于 1981 年提出的一种堆排序变体。它使用一种特殊的堆结构（Leonardo 堆）代替二叉堆，优势在于当输入数据已经部分有序时，可以实现接近线性时间的排序速度。平滑排序在最坏情况下仍然保持 O(n log n) 的时间复杂度。
13.3 优先队列
堆排序的核心思想——堆数据结构——最重要的应用并非排序本身，而是优先队列（Priority Queue）。许多操作系统中的进程调度（根据优先级选择下一个运行的进程）、图算法中的 Dijkstra 最短路径算法和 Prim 最小生成树算法、事件驱动模拟系统等，都依赖于堆来实现高效的优先队列操作。
十四、面试常见问题
14.1 基本概念题
- Q：堆排序是稳定的吗？A：不是，因为存在长距离的元素交换，会破坏相等元素的相对顺序。
- Q：建堆的时间复杂度为什么是 O(n) 而不是 O(n log n)？A：因为大部分节点位于堆的底层，每个节点 heapify 的时间与高度成正比，求和后级数收敛到 O(n)。
- Q：堆排序的空间复杂度是多少？A：O(1)，堆排序是原地排序算法。
14.2 代码实现题
- Q：手写堆排序。A：参见第五章的完整实现代码。
- Q：如何在 O(n log k) 时间内从长度为 n 的数组中找到最大的 k 个元素？A：使用容量为 k 的最小堆进行维护，遍历数组元素，当前元素大于堆顶时弹出堆顶并加入新元素。时间复杂度 O(n log k)，空间复杂度 O(k)。
- Q：如何用堆实现中位数查找？A：使用两个堆——一个最大堆存储较小的一半，一个最小堆存储较大的一半，保持两个堆的大小平衡（或最大堆多一个元素），则最大堆的堆顶即为中位数。
# 用堆查找数组中最大的 k 个元素
import heapq
def find_k_largest(arr, k):
"""使用最小堆查找最大的 k 个元素"""
if k <= 0 or not arr:
return []
min_heap = arr[:k]
heapq.heapify(min_heap)
for x in arr[k:]:
if x > min_heap[0]:
heapq.heappushpop(min_heap, x)
return min_heap
# 测试
data = [3, 2, 1, 5, 6, 4]
print(find_k_largest(data, 3)) # 输出: [4, 5, 6]（顺序可能不同）
十五、核心要点总结
- 堆排序的本质：一种基于二叉堆数据结构的改进选择排序，利用堆 O(log n) 的取出最大值操作替代选择排序的 O(n) 线性扫描。
- 时间复杂度：建堆 O(n) + 排序 O(n log n) = 总时间 O(n log n)，最好、最坏、平均情况均为 O(n log n)。
- 空间复杂度：O(1)，完全原地排序，这是堆排序相对于归并排序的核心优势。
- 不稳定性：堆排序不是稳定排序，长距离元素交换会破坏相等元素的相对顺序。
- 建堆的关键：从最后一个非叶节点开始自底向上 heapify，时间复杂度为 O(n) 而非 O(n log n)。
- 排序过程：每次将堆顶（最大值）交换到末尾，对新的堆顶执行 heapify，循环 n-1 次。
- 对比其他算法：堆排序的常数因子大于快速排序和归并排序，实际运行较慢，但其最坏情况 O(n log n) + 原地排序的组合是独一无二的。
- 工程应用：堆排序的直接应用较少，但其核心思想——堆数据结构——是优先队列、Top-K 问题、中位数维护等经典问题的基础。
- Python heapq：生产环境中推荐使用
heapq.heapify、heapq.heappush、heapq.heappop 等标准库函数。
- Floyd 优化：Floyd 建堆算法通过减少比较次数来降低常数因子，是实际工程中采用的建堆方式。
十六、进一步思考
堆排序的发明距今已超过六十年，但它的核心思想仍然在计算机科学的各个领域发挥着重要作用。从操作系统的进程调度到网络路由算法，从数据库索引构建到大数据 Top-K 查询，堆无处不在。
学习堆排序不应止步于实现代码本身，更重要的是理解其背后的数据结构思维：如何通过巧妙的组织方式将数据操作的时间复杂度从 O(n) 降低到 O(log n)。这种思维方式可以迁移到许多其他问题中——例如，在 B 树中使用多路分支进一步降低树的高度，在斐波那契堆中使用"懒惰合并"策略优化摊还时间。
拓展阅读建议：
- 深入理解堆的变体：二项堆（Binomial Heap）、斐波那契堆（Fibonacci Heap）、配对堆（Pairing Heap）
- 学习堆在 Dijkstra 最短路径算法中的应用
- 了解堆排序与锦标赛排序（Tournament Sort）的关系
- 研究 Python heapq 模块的 C 语言实现源码