堆排序
堆排序（Heap Sort）是一种原地的比较型排序算法——它把数组组织成一棵完全二叉树（堆），反复「取堆顶极值 + 下沉恢复堆序」，从而把排序问题转化为「n 次取最值」问题。它的总复杂度由两段组成：建堆 O(n)（Floyd 自底向下调整）+ n 次交换并下沉 O(n log n)，总体 O(n log n)，且最坏、平均、最好一致——这是它区别于快排「最坏 O(n²)」的核心优势。它原地排序（O(1) 额外空间），代价是不稳定和缓存不友好（堆的下沉是大跨度跳跃访问，不像快排/归并那样顺序扫描）。
堆排序的全部考点都源于一个核心套路：升序用大根堆、降序用小根堆——先把整个数组建成大根堆（堆顶是最大值），再把堆顶与数组末尾交换、缩小堆规模、对新堆顶下沉恢复堆序；如此重复 n 次，最大值依次「沉」到数组末尾，最终得到升序数组。由此衍生三大主题：①算法实现（建堆的 O(n) 证明、下沉 sift down、升序为何用大根堆、为何原地）；②特性分析（O(n log n) 最坏保证、为何实际比快排慢、不稳定性、与快排/归并的取舍）；③工程应用（Top-K / 部分排序用堆优于全排、优先队列、外部排序归并）。注意本叶只讲「如何用堆来排序」——堆数据结构本身（完全二叉树定义、sift up/down、优先队列实现）在独立的堆叶讲，本叶直接复用「堆顶即极值、下沉恢复堆序」这两个结论。
评价
优点
- O(n log n) 最坏保证：最好、平均、最坏都是 O(n log n)，没有快排「有序/逆序输入退化到 O(n²)」的毛病——对最坏延迟敏感的场景（实时系统、拒绝服务攻击防御）更可靠。
- 原地排序 O(1) 额外空间：建堆和排序都在原数组上进行，只需常数个临时变量，不需要归并排序 O(n) 的辅助数组——空间效率优于归并。
- 建堆线性 O(n)：Floyd 自底向下建堆是 O(n) 而非 O(n log n)，这是堆排序「预处理段」的高效保证（虽然总复杂度仍由 n 次下沉主导）。
- 天然支持 Top-K / 部分排序：只取前 k 个最大/最小元素时，建堆 + k 次取堆顶是 O(n + k log n)，远优于全排的 O(n log n)。
缺点
- 不稳定：相等的元素在「堆顶与末尾交换、远距离下沉」过程中相对顺序会被打乱——堆排序是不稳定排序（归并稳定，快排也不稳定）。
- 缓存不友好、常数大：堆的父子下标是
2i+1/2i+2的大跨度跳跃访问，不命中 CPU 缓存行，实际运行比同样 O(n log n) 的快排（顺序分区）慢 2~3 倍——这是它「理论好看、实际少用」的根本原因。 - 不像快排/归并那样「分治优雅」：堆排序是「全局建堆 + 反复取顶」，没有分治结构，难以像归并那样并行化、像快排那样利用局部性。
本叶地图
- 入门 —— 堆排序=建堆+反复取堆顶、原地 O(1) 空间、O(n log n) 一致、不稳定、与快排对比（最坏有保证但常数大/缓存不友好）
- 算法实现：建堆与排序 —— 升序用大根堆（堆顶换末尾再下沉）、建堆 O(n)（Floyd 自底向下）、n 次交换+下沉 O(n log n)、完整代码、为何原地
- 特性分析：最坏保证与应用 —— O(n log n) 最坏保证、为何实际比快排慢、不稳定原因、Top-K/部分排序用堆更优、优先队列场景
- 参考 —— 复杂度表、完整代码模板、与快排/归并对比、Top-K 应用、易错点（升序用大根堆/降序用小根堆）
交互演示
- 堆排序可视化演示 —— 建堆与反复取堆顶下沉的过程