public class HeapSort {
    
    /**
     * 堆排序
     * @param arr 待排序的整数数组
     */
    public static void sort(int[] arr) {
        int n = arr.length;
        
        // 第一阶段：建堆
        // 从最后一个非叶子节点开始，自底向上构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDown(arr, n, i);
        }
        
        // 第二阶段：排序
        // 反复将堆顶元素与堆末尾元素交换，然后缩小堆
        for (int i = n - 1; i > 0; i--) {
            // 将当前最大值（堆顶）交换到数组末尾
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            
            // 对剩余的堆进行调整
            siftDown(arr, i, 0);
        }
    }
    
    /**
     * 下沉操作：维护最大堆的性质
     * @param arr 数组
     * @param heapSize 当前堆的大小
     * @param root 需要调整的根节点索引
     */
    private static void siftDown(int[] arr, int heapSize, int root) {
        int largest = root;
        int leftChild = 2 * root + 1;
        int rightChild = 2 * root + 2;
        
        // 找出根节点、左子节点、右子节点中的最大值
        if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }
        if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }
        
        // 如果最大值不是根节点，交换并递归调整
        if (largest != root) {
            int temp = arr[root];
            arr[root] = arr[largest];
            arr[largest] = temp;
            siftDown(arr, heapSize, largest);
        }
    }
    
    /**
     * 迭代版本的下沉操作（避免递归开销）
     */
    private static void siftDownIterative(int[] arr, int heapSize, int root) {
        int current = root;
        while (true) {
            int largest = current;
            int leftChild = 2 * current + 1;
            int rightChild = 2 * current + 2;
            
            if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
                largest = leftChild;
            }
            if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
                largest = rightChild;
            }
            
            if (largest == current) {
                break;
            }
            
            int temp = arr[current];
            arr[current] = arr[largest];
            arr[largest] = temp;
            current = largest;
        }
    }
    
    /**
     * 堆排序（泛型版本）
     */
    public static <T extends Comparable<T>> void sortGeneric(T[] arr) {
        int n = arr.length;
        
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDownGeneric(arr, n, i);
        }
        
        for (int i = n - 1; i > 0; i--) {
            T temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            siftDownGeneric(arr, i, 0);
        }
    }
    
    private static <T extends Comparable<T>> void siftDownGeneric(T[] arr, int heapSize, int root) {
        int current = root;
        while (true) {
            int largest = current;
            int leftChild = 2 * current + 1;
            int rightChild = 2 * current + 2;
            
            if (leftChild < heapSize && arr[leftChild].compareTo(arr[largest]) > 0) {
                largest = leftChild;
            }
            if (rightChild < heapSize && arr[rightChild].compareTo(arr[largest]) > 0) {
                largest = rightChild;
            }
            
            if (largest == current) {
                break;
            }
            
            T temp = arr[current];
            arr[current] = arr[largest];
            arr[largest] = temp;
            current = largest;
        }
    }
}