数据结构与算法 / 系统课时

建堆与堆排序

建堆与堆排序

堆排序把数组先转换为最大堆,再反复把堆顶最大值移动到数组末尾。完成本课后,你将理解为什么自底向上建堆是 O(n)O(n),并能实现时间复杂度稳定为 O(nlog⁡n)O(n \log n)、额外空间为 O(1)O(1) 的原地排序。

学习目标

  • 掌握自底向上建堆的起始位置与执行顺序
  • 使用最大堆实现原地升序堆排序
  • 区分建堆复杂度、排序复杂度与算法稳定性

从无序数组到最大堆

数组的下标布局天然对应完全二叉树。所有下标大于等于 n / 2 的节点都是叶节点,单个叶节点已经满足堆性质,因此建堆只需从最后一个非叶节点 n / 2 - 1 开始,按下标递减执行向下堆化,直到根节点。

自底向上建堆与原地堆排序过程

建成最大堆后,数组首元素是当前最大值。将它与堆区间最后一个元素交换后,最大值便进入最终位置。随后把堆大小减一,并只对根节点执行一次向下堆化。重复这一过程,已排序区从右向左逐步扩大。

为什么建堆是线性时间

容易产生的误解是:建堆对大约 n / 2 个节点调用一次 O(log⁡n)O(\log n) 的向下堆化,所以复杂度一定是 O(nlog⁡n)O(n \log n)。这个估算忽略了不同节点能够下沉的高度不同。

靠近叶子的节点数量多,但最多只移动一两层;靠近根的节点可能移动很多层,但数量很少。把所有节点的实际移动上界相加,可得到:

∑h=0⌊log⁡2n⌋n2h+1⋅O(h)=O(n)\sum_{h=0}^{\lfloor \log_2 n \rfloor} \frac{n}{2^{h+1}} \cdot O(h) = O(n)

因此,自底向上建堆的时间复杂度是 O(n)O(n)。排序阶段需要进行约 n - 1 轮,每轮交换为 O(1)O(1),向下堆化为 O(log⁡n)O(\log n),总时间复杂度为 O(nlog⁡n)O(n \log n)。

完整可运行示例

下面的 Java 17 示例使用最大堆完成升序排序。buildMaxHeap 只处理非叶节点,heapSort 每轮缩小有效堆区间,不创建辅助数组。

java
import java.util.Arrays;

public class HeapSortDemo {

    public static void buildMaxHeap(int[] array) {
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            siftDown(array, array.length, i);
        }
    }

    public static void heapSort(int[] array) {
        buildMaxHeap(array);

        for (int end = array.length - 1; end > 0; end--) {
            // 堆顶是当前最大值,交换后进入最终位置
            swap(array, 0, end);
            siftDown(array, end, 0);
        }
    }

    private static void siftDown(int[] array, int size, int index) {
        while (true) {
            int largest = index;
            int left = 2 * index + 1;
            int right = 2 * index + 2;

            if (left < size && array[left] > array[largest]) {
                largest = left;
            }
            if (right < size && array[right] > array[largest]) {
                largest = right;
            }
            if (largest == index) {
                return;
            }

            swap(array, index, largest);
            index = largest;
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        int[] values = {4, 10, 3, 5, 1};

        int[] heapView = Arrays.copyOf(values, values.length);
        buildMaxHeap(heapView);
        System.out.println("最大堆: " + Arrays.toString(heapView));

        heapSort(values);
        System.out.println("升序结果: " + Arrays.toString(values));
    }
}

运行命令:

bash
javac HeapSortDemo.java
java HeapSortDemo

预期输出:

text
最大堆: [10, 5, 3, 4, 1]
升序结果: [1, 3, 4, 5, 10]

复杂度与工程取舍

阶段 时间复杂度 额外空间
自底向上建堆 O(n)O(n) O(1)O(1)
排序阶段 O(nlog⁡n)O(n \log n) O(1)O(1)
整体 O(nlog⁡n)O(n \log n) O(1)O(1)

堆排序的最好、平均和最坏时间复杂度都为 O(nlog⁡n)O(n \log n),不会像朴素快速排序那样在极端输入下退化到 O(n2)O(n^2)。它还能原地完成排序,但通常缓存局部性弱于归并排序和快速排序,并且不是稳定排序:交换堆顶与堆尾可能改变相等元素的原始相对顺序。

若目标是降序排列,可以构建最小堆并采用同样过程;也可以先得到升序结果再反转数组。前者能直接复用堆排序结构,但所有比较方向必须保持一致。

常见错误与验证

最常见的边界错误是从 array.length / 2 开始建堆。该位置已经是第一个叶节点,虽然多执行一次通常不会破坏结果,但会增加无意义操作;正确起点是 array.length / 2 - 1。

排序阶段调用向下堆化时,size 必须传入当前的 end,而不是完整数组长度。交换到右侧的元素已经进入最终位置,如果仍把它纳入堆区间,后续堆化会破坏已排序部分。

验证时可先单独调用 buildMaxHeap,检查根节点是否为全局最大值,并检查每个父节点是否不小于子节点;再执行完整排序,确认结果单调不降且元素数量、总和或频次没有变化。

本课练习

  1. 为示例增加每一轮排序后的数组输出,要求明确展示“堆区间”和“已排序区间”的边界。
  2. 将实现改为最小堆,并输出降序数组。验收条件是输入 [4, 10, 3, 5, 1] 后得到 [10, 5, 4, 3, 1]。
  3. 使用包含重复值的数组 [5, 1, 5, 3, 1] 测试排序结果,并记录相同值对象的原始顺序是否保持,以验证堆排序不稳定的特点。

本课总结

  • 自底向上建堆从最后一个非叶节点开始,总时间复杂度为 O(n)O(n)
  • 堆排序通过交换堆顶、缩小堆区间和重新堆化完成原地排序
  • 整体时间复杂度为 O(nlog⁡n)O(n \log n),额外空间为 O(1)O(1),但算法不稳定

下一课预告

完成堆排序后,下一阶段可以继续学习优先队列的接口设计与典型应用,理解如何把堆的插入、取顶和删除能力封装为可复用的数据结构。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

建堆与堆排序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通