LeetCode 补充题 6. 手撕堆排序

Categories:

题目描述
思路分析
1. 解法一：堆排序（推荐）
相似题目

题目描述

✅ 补充题 6. 手撕堆排序

思路分析

解法一：堆排序（推荐）

核心思路：

堆排序分两个阶段，利用大顶堆（父节点 ≥ 子节点）实现升序排序：

阶段一：建堆

从最后一个非叶节点（下标 n/2 - 1）开始，从右到左逐个执行下沉（heapify）操作，将无序数组调整为大顶堆。时间复杂度 O(n)。

阶段二：排序（反复提取堆顶）

将堆顶（最大值 nums[0]）与末尾元素交换，堆大小减 1，再对新堆顶执行 heapify 恢复堆性质。重复 n-1 次后，数组有序。

heapify（下沉）逻辑：

找当前节点 i 与左右子节点中的最大值 largest

若 largest != i：交换 nums[i] 和 nums[largest]，递归对 largest 继续下沉

完全二叉树节点编号：下标 i 的左子节点为 2i+1，右子节点为 2i+2，父节点为 (i-1)/2。

复杂度分析：

时间复杂度：O(n log n)，建堆 O(n) + 每次提取堆顶 O(log n) × n 次

空间复杂度：O(log n)，递归 heapify 的栈深度

class Solution {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        // 建堆：从最后一个非叶节点开始，向下堆化
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(nums, n, i);
        }
        // 排序：将堆顶（最大值）依次移到末尾
        for (int i = n - 1; i > 0; i--) {
            int tmp = nums[0];
            nums[0] = nums[i];
            nums[i] = tmp;
            heapify(nums, i, 0);
        }
        return nums;
    }

    private void heapify(int[] nums, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && nums[left] > nums[largest]) {
            largest = left;
        }
        if (right < n && nums[right] > nums[largest]) {
            largest = right;
        }
        if (largest != i) {
            int tmp = nums[i];
            nums[i] = nums[largest];
            nums[largest] = tmp;
            // 递归对被交换的子节点继续下沉
            heapify(nums, n, largest);
        }
    }
}

func sortArray(nums []int) []int {
    n := len(nums)
    // 建堆：从最后一个非叶节点开始，向下堆化
    for i := n/2 - 1; i >= 0; i-- {
        heapify(nums, n, i)
    }
    // 排序：将堆顶（最大值）依次移到末尾
    for i := n - 1; i > 0; i-- {
        nums[0], nums[i] = nums[i], nums[0]
        heapify(nums, i, 0)
    }
    return nums
}

func heapify(nums []int, n, i int) {
    largest := i
    left, right := 2*i+1, 2*i+2
    if left < n && nums[left] > nums[largest] {
        largest = left
    }
    if right < n && nums[right] > nums[largest] {
        largest = right
    }
    if largest != i {
        nums[i], nums[largest] = nums[largest], nums[i]
        // 递归对被交换的子节点继续下沉
        heapify(nums, n, largest)
    }
}

相似题目

题目	难度	考察点
215. 数组中的第K个最大元素	中等	堆/快速选择
347. 前 K 个高频元素	中等	小顶堆维护 Top K
23. 合并 K 个升序链表	困难	优先队列（堆）合并
295. 数据流的中位数	困难	大小顶堆维护中位数
373. 查找和最小的 K 对数字	中等	优先队列
912. 排序数组	中等	各类排序算法实现

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/47296054