LeetCode 补充题 6. 手撕堆排序
题目描述
给定整数数组
nums，请将其按非递减顺序排列并返回，所有元素及其重复次数都要保留。本补充题沿用力扣「排序数组」的输入输出，要求手动实现堆排序，不能直接调用内置排序函数。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
-
1 <= nums.length <= 5 * 10^4。 -
-5 * 10^4 <= nums[i] <= 5 * 10^4。 - 力扣原题要求 O(n log n) 时间，并尽量减少额外空间。
题意分析
将整数数组按从小到大的顺序排列，重复元素全部保留。本题要求手写堆排序，不能用库函数直接完成排序；目标是在 $O(n\log n)$ 时间内，尽量少用额外空间。
数组中的元素不需要变成链式二叉树，仍然存放在原数组中。我们只调整元素位置，最终返回升序数组。
解法：原地大根堆排序
核心思路
[!blue]
把数组前
size个位置看成一棵完全二叉树：下标root的左右孩子分别是2 * root + 1、2 * root + 2。大根堆要求每个父节点都不小于孩子，由此根节点不小于所有后代，数组首元素就是堆中的最大值。排序时维护两部分：
[0, end]是尚未排序的大根堆，后面是已经就位的有序后缀。把堆顶与end交换，就把剩余元素中的最大值放到了最终位置；再将堆大小缩为end，只处理[0, end)。后缀中的元素都不小于堆中元素，后续不会再移动它们。交换后只有新根可能破坏堆性质。
heapify比较根和两个有效孩子，若根已经最大就结束；否则将较大的孩子换上来，让较小的原根继续下沉。选择较大孩子，才能使换上来的值同时不小于另一个孩子；两棵孩子子树原本都满足堆性质，交换只会影响较小值落下的那棵子树，因此问题只沿下沉的那一条路径继续。初始数组还不是堆，需要先建堆。叶子本身就是堆，因此从最后一个非叶子节点
n / 2 - 1开始倒序下沉。处理某个父节点时，它的两棵孩子子树已经处理完，恰好满足heapify的前提。建堆后反复取出最大值，直到堆只剩一个元素，整个数组便升序有序。
解题步骤
- 从
n / 2 - 1倒序到0，以整个数组长度为堆大小，对各非叶子节点执行下沉。- 下沉时先检查孩子下标是否小于
size，再选出根和有效孩子中的最大值；根不是最大时交换，并从被换下去的位置继续。- 从
end = n - 1向前推进，每次交换堆顶与nums[end]，把本轮最大值放到最终位置。- 调用
heapify(nums, end, 0)，排除已经就位的end，恢复剩余堆的性质。- 当
end到达0时停止，返回原数组。只有一个元素时，两轮循环都不执行。
代码实现
class Solution {
public int[] sortArray(int[] nums) {
for (int i = nums.length / 2 - 1; i >= 0; i--) {
heapify(nums, nums.length, i);
}
for (int end = nums.length - 1; end > 0; end--) {
swap(nums, 0, end);
// 末尾最大值已就位，下沉范围必须排除这个有序位置。
heapify(nums, end, 0);
}
return nums;
}
private void heapify(int[] nums, int size, int root) {
while (true) {
int largest = root;
int left = root * 2 + 1;
int right = root * 2 + 2;
if (left < size && nums[left] > nums[largest]) {
largest = left;
}
if (right < size && nums[right] > nums[largest]) {
largest = right;
}
if (largest == root) {
break;
}
// 将较大的孩子换上来，继续向下恢复大根堆。
swap(nums, root, largest);
root = largest;
}
}
private void swap(int[] nums, int i, int j) {
int value = nums[i];
nums[i] = nums[j];
nums[j] = value;
}
}
func sortArray(nums []int) []int {
for i := len(nums)/2 - 1; i >= 0; i-- {
heapify(nums, len(nums), i)
}
for end := len(nums) - 1; end > 0; end-- {
nums[0], nums[end] = nums[end], nums[0]
// 末尾最大值已就位，下沉范围必须排除这个有序位置。
heapify(nums, end, 0)
}
return nums
}
func heapify(nums []int, size int, root int) {
for {
largest := root
left := root*2 + 1
right := root*2 + 2
if left < size && nums[left] > nums[largest] {
largest = left
}
if right < size && nums[right] > nums[largest] {
largest = right
}
if largest == root {
break
}
// 下沉 root，直到以 root 为根的子树满足大根堆。
nums[root], nums[largest] = nums[largest], nums[root]
root = largest
}
}
复杂度分析
- 时间复杂度：$O(n\log n)$。自底向上建堆为 $O(n)$：高度至少为 $h$ 的节点数至多约为 $n/2^h$，把各次下沉的每一层费用累计，得到 $n/2+n/4+\cdots=O(n)$。排序阶段有 $n-1$ 次取堆顶，每次下沉最多 $O(\log n)$。
- 空间复杂度：$O(1)$，堆和有序后缀都复用输入数组，下沉使用迭代，只需固定数量的下标变量。
- 稳定性：不稳定，堆顶与末尾的长距离交换可能改变相等元素的相对顺序。
关键点总结
[!green]
- 大根堆让剩余最大值随时位于堆顶，把它依次放到末尾即可得到升序。
- 下沉的前提是两个孩子子树已经成堆，所以本实现从最后一个非叶子节点倒序建堆。
size是堆区不包含的右边界，后缀中已就位的元素不能再参加比较。- 交换后只修复从根向下的一条路径，无需重建整个堆。
易错点总结
[!yellow]
- 取出最大值后仍把数组总长度传给下沉，会把刚就位的最大值重新拉回堆中；新堆大小应为
end。- 看到某个孩子比根大就立即交换，可能没有选中两个孩子中较大的一个，换上来的父节点仍然不满足堆性质。
- 在孩子子树尚未成堆时，从根向下只各做一次下沉，不能保证初始建堆正确；这里要按下标倒序处理非叶子节点。
- 读取孩子值前没有检查
< size，会越界或者把有序后缀当作堆的一部分。- 用小根堆却仍将堆顶放到末尾，会得到降序；升序的这套放置方式对应大根堆。
- 把一次下沉的 $O(\log n)$ 直接乘以全部节点作为建堆的精确量级，忽略了多数节点高度很小，自底向上建堆实际为 $O(n)$。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 215. 数组中的第K个最大元素 | 中等 | 大小k的堆可只保留TopK，本题大顶堆不断把最大值放入末尾已排序区。 |
| 1046. 最后一块石头的重量 | 简单 | 同样复用堆顶移除及下沉调整，原题还会把碰撞后的新值重新插入。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！