8.4.2 堆排序、堆的插入删除

堆是完全二叉树。升序堆排建大根堆，反复交换堆顶与末尾并向下调整剩余堆。建堆可自最后非叶向前，O(n)。

手工推演与代码

[4,1,3,2]建大堆可得[4,2,3,1]；交换4与1，调整前三项得[3,2,1,4]。

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

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。孩子下标公式混用0/1基；调整范围包含已排尾部；把建堆写O(nlogn)。

迁移训练

0基下标i的孩子是2i+1、2i+2。n=7最后非叶下标2。