堆排序

堆排序属于选择排序，利用堆这种数据结构进行排序。

堆的概念

堆是一棵完全二叉树，分为两种：

• 大根堆（大顶堆）：任一结点的值都大于等于其孩子结点的值
• 小根堆（小顶堆）：任一结点的值都小于等于其孩子结点的值

基本思想

1. 将待排序序列构造成初始堆（大根堆）
2. 输出堆顶元素（最大值），与堆尾元素交换
3. 调整剩余元素为新堆
4. 重复直到全部输出

复杂度

• 时间复杂度：$O(n\log n)$（建堆 $O(n)$，每次调整 $O(\log n)$）
• 稳定性：不稳定
• 空间复杂度：$O(1)$

向具有 $n$ 个关键字的堆中插入或删除一个元素的时间复杂度均为 $O(\log n)$。