public class 堆排序 {
    void HeapSort(int[] arr) {
        for(int i = arr.length / 2; i >= 0; i--) {
            HeapAdjust(arr, i, arr.length - 1);
        }
        for(int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            HeapAdjust(arr, 0, i - 1);
        }
    }
    
    private void HeapAdjust(int[] arr, int s, int m) {
        int temp = arr[s];
        for(int j = 2 * s; j <= m; j *= 2) {
            if(j < m && arr[j] < arr[j + 1])
                ++j;
            if(temp >= arr[j])
                break;
            arr[s] = arr[j];
            s = j;
        }
        arr[s] = temp;
    }
    
    private void swap(int[] arr, int a, int b) {
        arr[a] = arr[a] ^ arr[b] ^ (arr[b] = arr[a]);
    }
    public static void main(String[] args) {
        int[] arr = {90,70,80,60,10,40,50,30,20};
        堆排序 s = new 堆排序();
        s.HeapSort(arr);
        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

    }

}