8.4 堆排序、堆的插入删除·选择题讲评

堆排最坏nlogn、辅助空间O(1)、不稳定。插入堆向上调整，删除堆顶用末元素补位后向下调整。

手工推演与代码

大根堆只能保证父不小于孩子，数组并非整体降序。

代码实现必须保持当前有序区、堆区或归并段的不变量，并对空数组、单元素、重复键和逆序输入测试。

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。把堆中序当有序；从叶结点开始逐个下沉；删除任意元素不修复。

迁移训练

大根堆[9,7,8,1]删顶后末元素1补位，向下与8交换。