堆排序（Heap Sort）是一种基于二叉堆数据结构的比较排序算法。它的时间复杂度为 O(n log n)，空间复杂度为 O(1)（原地排序），但不是稳定排序。

在 Java 中实现堆排序通常包括以下步骤：

1. 构建最大堆（Max Heap）：将数组调整成一个最大堆，使得每个父节点都大于或等于其子节点。
2. 重复提取堆顶元素：将堆顶（最大值）与末尾元素交换，然后对剩余元素重新调整为最大堆，直到整个数组有序。

✅ Java 实现代码如下：

public class HeapSort {

// 堆排序主方法
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);
        // 对前 i 个元素重新堆化（排除已排序部分）
        heapify(arr, i, 0);
    }
}

// 调整以 index 为根的子树为最大堆（假设子树已经是堆）
private static void heapify(int[] arr, int heapSize, int index) {
    int largest = index;           // 初始化最大值为根
    int left = 2 * index + 1;      // 左子节点
    int right = 2 * index + 2;     // 右子节点

    // 如果左子节点存在且大于根
    if (left  arr[largest]) {
        largest = left;
    }

    // 如果右子节点存在且大于当前最大值
    if (right  arr[largest]) {
        largest = right;
    }

    // 如果最大值不是根，则交换并继续堆化
    if (largest != index) {
        swap(arr, index, largest);
        heapify(arr, heapSize, largest); // 递归调整受影响的子树
    }
}

// 交换数组中两个元素
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 测试示例
public static void main(String[] args) {
    int[] arr = {12, 11, 13, 5, 6, 7};
    System.out.println("原始数组: " + java.util.Arrays.toString(arr));

    heapSort(arr);

    System.out.println("排序后数组: " + java.util.Arrays.toString(arr));
}

}

📌 输出示例：

原始数组: [12, 11, 13, 5, 6, 7]
排序后数组: [5, 6, 7, 11, 12, 13]

💡 补充说明：

• heapify 函数用于维护堆性质。
• 初始建堆从 n/2 - 1 开始，因为这是最后一个非叶子节点的索引（完全二叉树性质）。
• 每次将最大值放到末尾后，堆的大小减一。

如需实现最小堆排序（升序变降序），只需将 heapify 中的比较方向反过来即可。

需要我提供非递归版 heapify 或 泛型版本 吗？