堆排序

LeetCode 912 https://leetcode.cn/problems/sort-an-array/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是手撕堆排序，使用最大堆。在本题中因为不会有新的元素插入，只需要实现自顶向下修复堆的操作即可。建堆时从最后一个非叶子结点开始，依次调用 repair 函数。然后每次将堆顶元素与堆的最后一个元素交换，堆的大小减一，修复堆。最后数组即为升序排列。反之，如果降序排列使用最小堆。 时间复杂度：O(nlogn)。初始化建堆的时间复杂度为 O(n)，建完堆以后需要进行 n−1 次调整，一次调整的时间复杂度为 O(logn)，那么 n−1 次调整即需要 O(nlogn) 的时间复杂度。因此，总时间复杂度为 O(n+nlogn)=O(nlogn)。 空间复杂度：O(1)。只需要常数的空间存放若干变量。 ...

本文介绍堆排序的实现方法，题目选择洛谷的 P1177。 本题使用小根堆，先把所有的元素都 push 进去，然后每次取出堆顶输出并弹掉堆顶，直到堆空为止。 堆的实现需要两个修复操作。当把结点插入堆时，首先将结点放到尾部，这时可能不满足小根堆的性质，因此需要自底向上修复堆。修复的边界条件是 x 已经是根结点或者 x 大于他的父结点。 当删除堆顶元素时，将堆顶元素和尾部元素交换，删除尾部元素，这时也可能不满足小根堆的性质，因此需要自顶向下修复堆。修复的边界条件是 x 已经是叶子结点或者 x 小于他的儿子中的最小值。 堆排序整体的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。 ...