堆排序：基于堆结构的高效排序，吃透 “建堆 + 调整” 核心逻辑

堆排序是结合 “堆数据结构” 与 “选择排序” 思想的高效排序算法，凭借 O (n log n) 的稳定时间复杂度、原地排序的特性，成为无需稳定性场景下的优质选择。它通过构建大顶堆（升序）/ 小顶堆（降序），反复提取堆顶最值元素并调整堆结构，最终实现数组有序，是理解堆应用的核心范例，也是面试高频考察的高级排序算法。

一、堆排序是什么？

堆排序的核心是 “堆”—— 先将无序数组构建为大顶堆（升序排序），此时堆顶为数组最大值；再将堆顶元素与数组末尾元素交换，缩小堆的范围并重新调整堆结构，重复此过程直到堆的范围为 1，数组即完全有序。

核心思想：
建堆：将无序数组构建为大顶堆（父节点值≥子节点值）；
排序：交换堆顶（最大值）与当前堆的最后一个元素，缩小堆范围；
调堆：对新的堆顶执行 “下沉调整”，恢复大顶堆特性；
重复：直到堆范围仅含一个元素，排序完成。

效率与特性：

时间复杂度：O(n log n)（建堆 O (n) + 调堆 O (n log n)，始终稳定）
空间复杂度：O(1)（原地排序，仅递归 / 迭代调堆的少量开销）
排序特性：不稳定排序（相等元素相对位置可能改变）、原地排序

适用场景：
适合大规模数据排序、Top K 问题（如找前 10 大元素）；无需稳定性的场景下，是归并排序的空间优化替代方案。

二、核心实现方式（大顶堆实现升序）

堆排序的核心是 “堆调整函数”，以下是易理解的经典实现，适配新手入门：

public class HeapSort {
    /**
     * 堆排序主方法：对数组进行升序排序
     *
     * @param arr 待排序的数组
     */
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int length = arr.length;

        // 1. 构建大顶堆：从最后一个非叶子节点开始，自下而上堆化
        for (int i = length / 2 - 1; i >= 0; i--) {
            heapify(arr, i, length);
        }

        // 2. 排序阶段：将堆顶最大值交换到数组末尾，再调整剩余部分为大顶堆
        for (int i = length - 1; i > 0; i--) { // i>0即可，i=0时只剩一个元素无需处理
            // 交换堆顶（最大值）和当前堆最后一个元素
            swap(arr, 0, i);
            // 对剩余未排序部分（0~i-1）重新堆化，堆大小变为i
            heapify(arr, 0, i);
        }
    }

    /**
     * 堆化方法：将以 parentIndex 为根的子树调整为大顶堆
     *
     * @param arr         存储堆结构的数组
     * @param parentIndex 待调整的父节点索引
     * @param heapSize    堆的有效大小（调整范围：0 ~ heapSize-1）
     */
    private static void heapify(int[] arr, int parentIndex, int heapSize) {
        int parentVal = arr[parentIndex]; // 保存当前父节点值
        int maxChildIndex = 2 * parentIndex + 1; // 左子节点索引

        // 循环向下调整，直到子节点超出堆的有效范围
        while (maxChildIndex < heapSize) {
            // 找到左右子节点中值更大的那个
            if (maxChildIndex + 1 < heapSize && arr[maxChildIndex] < arr[maxChildIndex + 1]) {
                maxChildIndex++; // 切换为右子节点
            }

            // 父节点 >= 最大子节点，满足大顶堆，无需继续调整
            if (parentVal >= arr[maxChildIndex]) {
                break;
            }

            // 父节点下沉：将最大子节点值赋给父节点
            arr[parentIndex] = arr[maxChildIndex];

            // 指针下移，继续检查下一层
            parentIndex = maxChildIndex;
            maxChildIndex = 2 * parentIndex + 1;
        }

        // 将父节点值放到最终正确位置
        arr[parentIndex] = parentVal;
    }

    /**
     * 辅助交换方法：避免重复代码，增加可读性
     */
    private static void swap(int[] arr, int a, int b) {
        if (a == b) {
            return;
        }
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    // 测试
    public static void main(String[] args) {
        int[] arr = {9,8,7,6,5,4,3,2,1};
        System.out.println("排序前：" + java.util.Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后：" + java.util.Arrays.toString(arr));
    }
}

三、必避的三个核心坑

堆排序的核心难点在堆结构的下标计算和调整逻辑，新手易踩这些关键坑：

1、非叶子节点起始下标： 建堆时需从 n/2 - 1 开始（而非 0），否则会遗漏大量节点的调整，导致堆构建失败；
2、堆调整边界： heapify 函数中需判断 left < heapSize/right < heapSize，避免子节点下标越界（堆范围随排序逐步缩小）；
3、递归 / 迭代选择： 递归版 heapify 易在大数据量下触发栈溢出，工程中建议改用迭代版（将递归改为循环）。

四、总结

1、堆排序核心逻辑是 “先构建大顶堆，再反复提取堆顶最值并调整堆结构”，时间复杂度始终稳定在 O (n log n)；
2、堆排序是原地、不稳定排序，适合 Top K 问题和无稳定性要求的大规模数据排序；
3、核心避坑点是找准非叶子节点起始下标、控制堆调整的边界、根据数据量选择递归 / 迭代版堆调整，避免越界和栈溢出。

堆排序：基于堆结构的高效排序，吃透 “建堆 + 调整” 核心逻辑