排序算法 HEAP SORT
堆排序.
建立最大堆，依次把堆顶最大值放到数组末尾。
时间O(n log n)额外空间O(1)稳定性不稳定
原理与执行逻辑
先将数组组织成最大堆，使堆顶始终是当前范围中的最大值。反复把堆顶放到范围末尾，再修复缩小后的堆。
执行步骤
- 从最后一个非叶节点向前执行下沉，建立最大堆。
- 交换堆顶与当前范围末尾，将最大值固定在右侧。
- 缩小堆范围，从根向下与较大的孩子交换，恢复堆性质。
- 重复取出最大值，直到堆范围只剩一个元素。
关键理解
堆内父节点不小于孩子；孩子下标为 2i + 1 和 2i + 2。已排好的后缀不参与下沉，堆本身不要求兄弟节点有序。
简短示例
最大堆 [5, 3, 4, 1] 取出 5 后得到 [1, 3, 4, 5]，在前三个元素中下沉恢复为 [4, 3, 1, 5]。
代码与执行动画
STEP 0 / 47function heapSort(arr) { function siftDown(root, size) { while (root * 2 + 1 < size) { let child = root * 2 + 1; if (child + 1 < size && arr[child + 1] > arr[child]) child++; if (arr[root] >= arr[child]) break; [arr[root], arr[child]] = [arr[child], arr[root]]; root = child; } } for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) siftDown(i, arr.length); for (let end = arr.length - 1; end > 0; end--) { [arr[0], arr[end]] = [arr[end], arr[0]]; siftDown(0, end); } return arr;}高亮对应当前步骤；源码对传入数组进行原地排序。
数组状态
升序 · 8 个元素比较 0实际交换 0数组写入 0当前区间 —
待排序当前操作已就位
下标显示在底部；柱体随元素移动，等值元素也保留独立身份。
0
准备排序
点击下一步或自动播放，观察数组从左到右升序排列的过程。
调整待排序数组
使用相同数据切换算法，观察比较与交换过程。
堆排序的执行规则
使用迭代下沉维护最大堆；左右孩子下标分别是 2i + 1 和 2i + 2。
交换次数仅统计两个不同位置的交换；可输入重复值。对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
- 对应题目912. 排序数组打开题目
练习建堆与交换堆顶后的下沉，满足 O(n log n) 排序要求。