堆排序

定义

堆排序是一种利用堆这种数据结构进行排序的算法。它先把数组构造成大顶堆，再反复取出堆顶最大值与末尾交换并缩小堆范围，最终得到升序序列。

原理

第一步自底向上建堆，时间为 O(n)。第二步循环：把堆顶（当前最大值）与堆的最后一个元素交换，堆大小减一，然后对新堆顶执行下沉调整恢复堆序，重复直到堆中只剩一个元素。整个过程在原数组上完成，不需要额外空间。堆排序是原地排序，但不稳定。

复杂度

• 时间复杂度（最好/平均/最坏）：O(n log n)
• 空间复杂度：O(1)
• 稳定性：不稳定

应用场景

• 对空间敏感、要求最坏性能可控的排序
• Top K 问题
• 优先队列的底层支撑