LeetCode 补充题 6. 手撕堆排序

约 6 分钟
文章信息 17 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 50-100 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 拼多多 商汤 高频面试题
标签
排序
目录

题目描述

✅ 补充题 6. 手撕堆排序

题意分析

输入一个整数数组，要求把它按升序排好并返回。题面挂在「排序数组」下，但面试官点名「手撕堆排序」，意味着调库排序、调优先队列都不算数，必须自己写出建堆和调整的每一行。

「手撕」还隐含两个约束信号：一是原地，除了几个循环变量不允许再开辅助数组；二是要经得起追问，面试官大概率会接着问「建堆为什么是线性时间」「为什么升序要用大顶堆」。

边界上要留意：空数组和单元素数组应直接返回；数组中允许出现重复元素，堆排序不保证相等元素的相对顺序，这一点后面复杂度与稳定性的追问里会用到。

解法：原地大根堆排序

核心思路

问题关键：原地升序排序需要反复取出未排序区间的最大值。大顶堆能让最大值始终位于下标 0，并在交换后用一次下沉恢复结构。

把数组看成完全二叉树：节点 i 的左右孩子是 2i+1、2i+2。维护大顶堆不变量：每个父节点都不小于孩子。排序时，前缀 [0,end] 是堆区，后缀 (end,n) 是已确定的有序区；把堆顶与 end 交换，就能把当前最大值放到最终位置。

heapify 假设根的左右子树已经是大顶堆，只让根与较大的孩子交换并继续下沉，因此只修复一条路径。自底向上从最后一个非叶子节点 n/2-1 建堆，正好满足这个前提。

升序选大顶堆，是因为最大值可以从数组头直接放到数组尾；若使用小顶堆，最小值和堆顶都占据数组前端，难以在同一数组中划分堆区和有序区。

解题步骤

  • 从 i = n/2-1 倒序到 0 调用 heapify，将整个数组建成大顶堆；更靠后的节点都是叶子，无需处理。
  • 下沉时比较根和两个有效孩子，找到最大值；若最大值仍是根则停止，否则交换并沿该孩子继续。
  • 从数组末尾向前遍历 end：交换 nums[0] 与 nums[end]，当前最大值进入最终位置。
  • 将堆大小缩为 end，只对根执行下沉；后缀有序区不再参与比较。
  • 当堆区只剩一个元素时，整个数组升序有序。

例如 [4,6,8,5,9] 建堆后为 [9,6,8,5,4]。首轮把 9 放到末尾，再对前 4 个元素沉根；重复后得到 [4,5,6,8,9]。

代码实现

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)$；随后执行 $n-1$ 次取堆顶，每次下沉最多 $O(\log n)$。
  • 空间复杂度：$O(1)$。堆和有序区都复用输入数组，下沉使用迭代实现。
  • 稳定性：不稳定。堆顶与末尾的长距离交换可能改变相等元素的相对顺序。

关键点总结

  • 升序用大顶堆：堆顶最大值逐个放到数组末尾。
  • 建堆必须从 n/2-1 倒序下沉；按节点高度加权求和，建堆总成本是 $O(n)$，不是 $O(n\log n)$。
  • 下沉必须先选左右孩子中的较大者，再决定是否交换。
  • 每轮交换后只有根可能破坏堆性质，因此只需从根向下修复，并排除已有序后缀。

易错点总结

  • 下沉仍传数组总长度：最大值刚放到末尾又会被拉回堆中；堆大小必须传 end，排除有序后缀。
  • 只比较一个孩子或先看到谁大就交换：如根和孩子为 [4,6,8]，应直接选择 8，否则交换后仍不满足大顶堆。
  • 建堆从上往下执行下沉：处理父节点时孩子子树尚未成堆，可能漏掉深层最大值；必须从最后一个非叶子节点倒序。
  • 孩子下标或边界错误：0 基数组的孩子是 2i+1、2i+2，且读取前必须检查 < size。
  • 误认为堆排序稳定：长距离交换会打乱相等元素的原顺序，堆排序不稳定。

相似题目

题目 难度 考察点
912. 排序数组 中等 同一题面，可对照手写快排与归并
215. 数组中的第K个最大元素 中等 只取第 $k$ 大，堆可提前停止不必全排
347. 前 K 个高频元素 中等 按频次建小顶堆做 Top K 筛选
703. 数据流中的第 K 大元素 简单 流式场景维护固定大小的小顶堆
239. 滑动窗口最大值 困难 堆解法需配合延迟删除处理过期元素