入门：建堆与反复取堆顶的原地排序
基于通用算法概念 · 核于 2026-07
速查
- 定义：堆排序是原地比较型排序——把数组建成一棵完全二叉树（堆），反复「取堆顶极值 + 下沉恢复堆序」，n 次取顶后整个数组有序。
- 核心套路：升序用大根堆（堆顶是最大值，换到末尾）、降序用小根堆（堆顶是最小值，换到末尾）——方向与堆的性质相反，是最高频易错点。
- 两段复杂度：建堆 O(n)（Floyd 自底向下 sift down）+ n 次交换并下沉 O(n log n)，总体 O(n log n)。
- 最坏一致：最好、平均、最坏都是 O(n log n)——没有快排「有序/逆序输入退化到 O(n²)」的毛病，这是它对快排的核心优势。
- 原地 O(1) 空间：建堆和排序都在原数组上，只用常数个临时变量，不需要归并排序的 O(n) 辅助数组。
- 不稳定：相等元素在「堆顶与末尾交换、远距离下沉」中相对顺序被打乱——堆排序是不稳定排序。
- 缓存不友好、常数大：堆父子下标
2i+1/2i+2是大跨度跳跃访问，不命中缓存行，实际比同 O(n log n) 的快排（顺序分区）慢 2~3 倍。 - 与快排对比：堆排序最坏有保证（O(n log n) vs 快排 O(n²)）但平均更慢（常数大、缓存差）——所以通用库（
sort()）首选快排/内省排序，堆排序用于「最坏延迟可控」或「Top-K」场景。 - 下标映射：0 基下标下，节点
i的父⌊(i-1)/2⌋、左子2i+1、右子2i+2——完全二叉树压平到数组的标准映射。 - 本叶边界：只讲「如何用堆来排序」；堆数据结构本身（完全二叉树定义、sift up/down、优先队列）见堆叶。
- 进阶顺序：算法实现 → 特性分析 → 参考。
一、一句话理解堆排序
堆排序 = 建堆 + 反复取堆顶。
1. 把数组 a[0..n-1] 建成大根堆（堆顶 a[0] 是最大值）
2. for i = n-1 downto 1:
swap(a[0], a[i]) // 当前最大值换到有序区末尾
siftDown(a, 0, i) // 对缩小后的堆（规模 i）下沉恢复堆序
3. 数组升序关键直觉：每轮把「当前堆的最大值」从堆顶换到「数组末尾」，然后堆规模减一、对新堆顶下沉。n 轮后，最大值、次大值、……依次沉到末尾，数组升序。
二、为什么升序用大根堆
这是初学者最易绕进死胡同的点。直觉上「要升序（小→大），应该用小根堆」，但堆排序恰恰相反——升序用大根堆。
原因在于「堆顶换到末尾」这个动作：大根堆的堆顶是最大值，把它换到数组末尾，末尾就成了「当前最大」，正好符合升序数组「末尾最大」的要求。堆规模不断缩小，最大值、次大值依次「沉」到末尾，最终整个数组从左到右升序。
若用小根堆排升序：堆顶是最小值，换到末尾后末尾是最小值——这恰好是降序，方向错了。所以口诀：排升序用大根堆（顶最大沉到底），排降序用小根堆（顶最小沉到底）。
三、核心复杂度
| 阶段 | 复杂度 | 说明 |
|---|---|---|
| 建堆（Floyd 自底向下） | O(n) | 从最后一个非叶子节点起逐个下沉，总和是 O(n)（不是 O(n log n)） |
| 排序（n 次交换+下沉） | O(n log n) | 每次下沉 ≤ O(log n)，共 n 次 |
| 总体 | O(n log n) | 由 n 次下沉主导，建堆段被吸收 |
| 额外空间 | O(1) | 原地，常数临时变量 |
| 最好/平均/最坏 | 一致 O(n log n) | 不退化（区别于快排最坏 O(n²)） |
注意：建堆虽然是 O(n)，但排序段 O(n log n) 更大，所以总复杂度仍是 O(n log n)——建堆的 O(n) 只是让「预处理」更省，不影响总量级。
四、原地 O(1) 空间是怎么做到的
堆排序的精妙之处在于「堆和有序区共用同一个数组」：
[ 堆区（无序，满足堆序） | 有序区（已排好，升序） ]- 建堆阶段：整个数组都是「堆区」。
- 排序每轮：
swap(a[0], a[i])把堆顶（堆区最大值）换到a[i]，然后a[i..n-1]自然成为「有序区」，a[0..i-1]是缩小后的「堆区」。 - 整个过程只在原数组上交换、下沉，不申请任何与 n 相关的额外空间——这是堆排序相对归并（要 O(n) 辅助数组）的空间优势。
五、与快排、归并的取舍
| 维度 | 堆排序 | 快排 | 归并排序 |
|---|---|---|---|
| 最好/平均 | O(n log n) | O(n log n) | O(n log n) |
| 最坏 | O(n log n) ✅ | O(n²) ❌ | O(n log n) |
| 额外空间 | O(1) ✅ | O(log n)（栈） | O(n) ❌ |
| 稳定性 | 不稳定 | 不稳定 | 稳定 ✅ |
| 缓存友好 | 差（跳跃）❌ | 好（顺序） ✅ | 好（顺序） |
| 实际速度 | 慢（常数大） | 最快 | 较快 |
一句话取舍：要最坏保证 + 原地 → 堆排序；要平均最快 → 快排；要稳定 → 归并。实际通用库（V8 sort、C++ std::sort）多用内省排序（introsort）——快排为主、递归过深时切堆排保证最坏、小区间切插入排序——正是三者优点的融合。
六、为什么堆排序「理论好看、实际少用」
堆排序有 O(n log n) 最坏保证 + O(1) 空间，理论上很完美，但工程上通用排序几乎都用快排/内省排序，原因在于：
- 缓存不友好：快排的分区是顺序扫描连续内存（缓存命中率高），堆排的下沉是
i → 2i+1的跳跃访问（缓存命中率低）。现代 CPU 缓存层级深，跳跃访问的代价远超顺序访问，导致堆排实际慢 2~3 倍。 - 常数大：每轮下沉要做两次子节点比较 + 一次父换子，分支预测差，指令数比快排分区多。
- 不稳定：需要稳定排序的场景（数据库、多关键字排序）不能直接用堆排。
所以堆排序的真实用武之地不是「通用排序」，而是：①最坏延迟敏感场景（实时系统、防 DoS）；②Top-K / 部分排序（只取前 k 个，不必全排）；③优先队列（动态维护极值）。
下一步
理解了堆排序「建堆 + 反复取堆顶」的整体框架后，下一步看它的算法实现细节——建堆的 O(n) 证明、下沉 sift down 的代码、升序用大根堆的完整流程，见算法实现：建堆与排序。