堆排序思想分享

public class HeapSort {
    public static void heapSort(int[] array) {
        int n = array.length;
        
        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }
        
        // 一个一个从堆顶取出元素，放到已排序区域
        for (int i = n - 1; i > 0; i--) {
            // 交换当前堆顶元素和当前未排序部分的最后一个元素
            swap(array, 0, i);
            
            // 调整剩下的堆，长度减 1
            heapify(array, i, 0);
        }
    }

    private static void heapify(int[] array, int n, int i) {
        int largest = i;        // 假设当前节点 i 是最大值
        int left = 2 * i + 1;   // 左子节点索引
        int right = 2 * i + 2;  // 右子节点索引
        
        // 如果左子节点存在且大于当前节点，则更新 largest
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }
        
        // 如果右子节点存在且大于当前节点，则更新 largest
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }
        
        // 如果 largest 不是当前节点 i，交换它们并继续调整
        if (largest != i) {
            swap(array, i, largest);
            heapify(array, n, largest);
        }
    }

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

    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6, 7};
        System.out.println("Original array: ");
        printArray(array);
        
        heapSort(array);
        
        System.out.println("Sorted array: ");
        printArray(array);
    }

    private static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Original array: 
12 11 13 5 6 7 
Sorted array: 
5 6 7 11 12 13