使用Java实现堆排序算法

堆排序是一种基于堆数据结构的高效排序算法，它利用大顶堆（父节点值大于子节点值的完全二叉树）每次取出最大值，逐步将数组排序。堆排序的时间复杂度为O(n log n)，空间复杂度为O(1)，是一种原地排序算法，适合处理大规模数据。

堆的概念¶

堆是一种特殊的完全二叉树，分为大顶堆和小顶堆：
- 大顶堆：每个父节点的值都大于或等于其子节点的值（如金字塔，顶部最大）。
- 小顶堆：每个父节点的值都小于或等于其子节点的值。

堆排序使用大顶堆，核心思想是：每次取出堆顶的最大值，放到数组末尾，再调整剩余元素形成新的大顶堆，重复操作直到数组有序。

实现步骤¶

构建大顶堆：将无序数组调整为大顶堆，使最大值位于堆顶（数组首元素）。
调整堆（heapify）：取出堆顶最大值后，调整剩余元素的结构，保持大顶堆性质。
排序过程：交换堆顶与数组末尾元素，缩小堆的范围，重复调整堆，直到排序完成。

核心函数实现¶

1. 调整堆（heapify）¶

功能：以指定节点为根，调整子树为大顶堆。
参数：数组、堆大小、当前节点索引。
逻辑：比较当前节点与左右子节点，将最大子节点上移，递归调整子树。

private static void heapify(int[] arr, int heapSize, int index) {
    int largest = index; // 假设当前节点是最大值
    int leftChild = 2 * index + 1; // 左子节点索引
    int rightChild = 2 * index + 2; // 右子节点索引

    // 找到左右子节点中的最大值
    if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
        largest = leftChild;
    }
    if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
        largest = rightChild;
    }

    // 若最大值不是当前节点，交换并递归调整子树
    if (largest != index) {
        int temp = arr[index];
        arr[index] = arr[largest];
        arr[largest] = temp;
        heapify(arr, heapSize, largest);
    }
}

2. 构建大顶堆¶

功能：从最后一个非叶子节点开始，逐步向前调整每个节点，使整个数组成为大顶堆。
逻辑：最后一个非叶子节点的索引为 n/2 - 1（n为数组长度），从该节点开始向前调用heapify。

private static void buildMaxHeap(int[] arr) {
    int n = arr.length;
    // 从最后一个非叶子节点开始调整
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

3. 堆排序主函数¶

功能：先构建大顶堆，再通过交换堆顶与末尾元素、调整堆，完成排序。
逻辑：
- 构建大顶堆后，最大值在堆顶（arr[0]）。
- 循环将堆顶元素与数组末尾元素交换，堆大小减1，调整剩余元素为大顶堆，重复直到排序完成。

public static void heapSort(int[] arr) {
    buildMaxHeap(arr); // 第一步：构建大顶堆

    // 第二步：排序过程
    for (int i = arr.length - 1; i > 0; i--) {
        // 交换堆顶（最大值）与当前末尾元素
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 调整剩余元素为大顶堆
        heapify(arr, i, 0);
    }
}

完整代码与测试¶

import java.util.Arrays;

public class HeapSort {

    // 调整子树为大顶堆
    private static void heapify(int[] arr, int heapSize, int index) {
        int largest = index;
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;

        if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }
        if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }

        if (largest != index) {
            int temp = arr[index];
            arr[index] = arr[largest];
            arr[largest] = temp;
            heapify(arr, heapSize, largest);
        }
    }

    // 构建大顶堆
    private static void buildMaxHeap(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
    }

    // 堆排序主函数
    public static void heapSort(int[] arr) {
        buildMaxHeap(arr);
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }

    // 测试
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("排序前：" + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
    }
}

输出结果¶

排序前：[12, 11, 13, 5, 6, 7]
排序后：[5, 6, 7, 11, 12, 13]

总结¶

堆排序通过构建大顶堆和反复调整堆，实现了高效排序。其核心在于heapify函数的递归调整，确保每次操作都能维护堆的性质。堆排序适用于大规模数据排序，尤其在空间受限的场景中表现优异。初学者可通过逐步理解构建堆、调整堆、排序三个步骤，掌握其实现逻辑。