← 返回首页 📖 📖 Wiki知识库
📐 学习维度 本篇是 📖 📖 Wiki知识库 🏠 首页 🛤️ 学习路径 📚 全部文章

Java排序算法面试手写精讲 - 四、堆排序

本文是 Java排序算法面试手写精讲 的分章阅读版。

四、堆排序

核心思想

构建大顶堆 -> 堆顶最大元素与末尾交换 -> 缩小堆范围 -> 重新堆化(siftDown) -> 重复。

基础版(面试快写)


public static void heapSort(int[] arr) {
    int n = arr.length;
    // 1. 建大顶堆(从最后一个非叶子节点开始)
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    // 2. 逐个取出堆顶最大值
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);      // 堆顶与末尾交换
        heapify(arr, i, 0);   // 重新堆化(堆大小减1)
    }
}

private static void heapify(int[] arr, int size, int root) {
    int largest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;

    if (left < size && arr[left] > arr[largest]) largest = left;
    if (right < size && arr[right] > arr[largest]) largest = right;

    if (largest != root) {
        swap(arr, root, largest);
        heapify(arr, size, largest);  // 递归堆化子树
    }
}

生产级堆排序(siftDown迭代版 + 完整注释)


public class HeapSort {

    /**
     * 堆排序入口
     * 时间复杂度:建堆O(n) + n次siftDown O(nlogn) = O(nlogn)
     * 空间复杂度:O(1) 原地排序
     * 不稳定:siftDown可能改变相等元素的相对顺序
     */
    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int n = arr.length;

        // Phase 1: 建堆(Floyd建堆法)
        // 从最后一个非叶子节点开始,自底向上siftDown
        // 为什么从n/2-1开始?因为索引n/2到n-1都是叶子节点,已经是合法的堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDown(arr, n, i);
        }

        // Phase 2: 逐个提取最大值
        // 每次将堆顶最大元素交换到数组末尾,然后缩小堆的范围
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);         // 堆顶(最大值)放到已排序区域
            siftDown(arr, i, 0);     // 对新的堆顶执行siftDown,堆大小=i
        }
    }

    /**
     * 下沉操作(迭代版,避免递归栈开销)
     *
     * @param arr  数组
     * @param size 当前堆的有效大小(不是数组长度)
     * @param i    需要下沉的节点索引
     *
     * 逻辑:将arr[i]与其较大的子节点比较,如果比子节点小则交换,直到满足堆性质
     */
    private static void siftDown(int[] arr, int size, int i) {
        int half = size >>> 1;  // 只需要遍历到非叶子节点
        while (i < half) {
            int child = (i << 1) + 1;  // 左子节点 = 2*i+1
            int right = child + 1;      // 右子节点 = 2*i+2

            // 找出两个子节点中较大的
            if (right < size && arr[right] > arr[child]) {
                child = right;
            }

            // 如果父节点已经 >= 最大的子节点,堆性质已满足
            if (arr[i] >= arr[child]) break;

            // 否则交换,继续下沉
            swap(arr, i, child);
            i = child;
        }
    }

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

建堆为什么是O(n)而不是O(nlogn)? 直觉上n/2个节点每个siftDown最多logn,应该是O(nlogn)。但实际大部分节点在底层,siftDown深度很小:第k层有2^k个节点,每个下沉h-k层。总移动次数 = sum(2^k * (h-k)) = O(n)。数学证明比直觉更紧。

面试关联: 堆排序与Top-K问题直接相关——用小顶堆维护K个最大元素,时间复杂度O(nlogk)。Java的PriorityQueue底层就是堆结构,默认小顶堆。


相关页面