public class HeapSort {
    public static final int[] ARRAY = {35, 63, 48, 9, 86, 24, 53, 11};
    public static int[] sort(int[] array) {
        //數(shù)組的長度
        int length = array.length;
        if (length < 2) return array;
        //首先構建一個最大堆
        buildMaxHeap(array);
        //調(diào)整為最大堆之后，頂元素為最大元素并與微元素交換
        while (length > 0) {//當lenth <= 0時，說明已經(jīng)到堆頂
            //交換
            swap(array, 0, length - 1);
            length--;//交換之后相當于把樹中的最大值彈出去了，所以要--
            //交換之后從上往下調(diào)整使之成為最大堆
            adjustHeap(array, 0, length);
        }
        return array;
    }
    //對元素組構建為一個對應數(shù)組的最大堆
    private static void buildMaxHeap(int[] array) {
        //在之前的分析可知，最大堆的構建是從最后一個非葉子節(jié)點開始，從下往上，從右往左調(diào)整
        //最后一個非葉子節(jié)點的位置為：array.length/2 - 1
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            //調(diào)整使之成為最大堆
            adjustHeap(array, i, array.length);
        }
    }
    /**
     * 調(diào)整
     * @param parent 最后一個非葉子節(jié)點
     * @param length 數(shù)組的長度
     */
    private static void adjustHeap(int[] array, int parent, int length) {
        //定義最大值的索引
        int maxIndex = parent;
        //parent為對應元素的位置（數(shù)組的索引）
        int left = 2 * parent + 1;//左子節(jié)點對應元素的位置
        int right = 2 * (parent + 1);//右子節(jié)點對應元素的位置
        //判斷是否有子節(jié)點，再比較父節(jié)點和左右子節(jié)點的大小
        //因為parent最后一個非葉子節(jié)點，所以如果有左右子節(jié)點則節(jié)點的位置都小于數(shù)組的長度
        if (left < length && array[left] > array[maxIndex]) {//左子節(jié)點如果比父節(jié)點大
            maxIndex = left;
        }
        if (right < length && array[right] > array[maxIndex]) {//右子節(jié)點如果比父節(jié)點大
            maxIndex = right;
        }
        //maxIndex為父節(jié)點，若發(fā)生改變則說明不是最大節(jié)點，需要交換
        if (maxIndex != parent) {
            swap(array, maxIndex, parent);
            //交換之后遞歸再次調(diào)整比較
            adjustHeap(array, maxIndex, length);
        }
    }
    //交換
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}