堆排序Heapsort
先建堆，再反复将最大元素移到未排序区间末尾。
- 核心约束
- 未处理区间保持堆序，尾部已经有序。
- 适用问题
- 需要最坏时间保证且额外空间有限的排序。
- 边界与取舍
- 通常不稳定，局部性与常数成本影响实际表现。
时间与空间#
n 为元素数；数组表示二叉堆。
- 时间复杂度
- 平均 / 最坏
- 辅助空间
- 原地迭代实现
先 建堆，再反复交换堆顶并下沉。通常不稳定；数据相等时的最好情况取决于下沉实现，不作统一线性或对数线性承诺。
工程中的应用#
1 个案例 · 附源码SwarmKit 的调度决策树在叶子中使用 nodeMaxHeap，把候选节点整理为从优到劣的顺序。
附源码片段 · 调度与资源分配
基础原理参考资料
Princeton · Heap原地堆排序的时间、空间和稳定性。