public class HeapSort {
    public static void main(String[] args) {
        int array[] = {5, 15, 10, 20, 13};
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }

    //堆排序(從小到大排序，大頂堆模式實現)
    public static void heapSort(int array[]){
        int temp = 0;
        /*
        在二叉樹中由下到上，把二叉樹數組調整成大頂堆數組
        array.length/2-1 ：指向最後一個非葉子節點
         */
        for (int i = array.length/2-1; i>=0; i--){
            adjustHeap(array, i, array.length);
        }

        /*
        在經過調整後，數組的第一個索引0的值必定是數組調整長度內最大的值，
        因為是從小到大進行排序，所以要把索引0的值放到調整長度內最後一個索引的值，
        即放到調整長度-1的索引位置
         */
        for (int j = array.length-1; j>0; j--){
            //將調整長度內最大值array[0]和調整長度內最後位置的值array[j]進行交換
            temp = array[j];
            array[j] = array[0];
            array[0] = temp;
            /*
            又因為經過交換後，大頂堆的結構會被破壞，所以要重新進行調整，
            調整起點應為根節點(因為根節點發生了變化)，即數組0下標位置，
            而array[j]已經是不需要調整的了，所以調整長度為j(因為在調整方法里j參數是被當作長度處理的，所以無需-1)
             */
            adjustHeap(array,0, j);
        }
    }

    /**
     * 將數組調整成大頂堆數組
     * @param array 需調整的數組
     * @param i 索引指針，開始指向傳入的非葉子節點，後面指向最後進行交換(插入)的節點
     * @param length 需調整的長度，即調整的元素個數，從0下標索引開始
     */
    public static void adjustHeap(int array[], int i, int length){
        //輔助變數，存儲傳入的非葉子節點的值
       int temp = array[i];

       /*
       遍歷傳入的非葉子節點下的子節點，i*2+1為左節點，i*2+2為右節點
       如果該節點不是非葉子節點則退出循環
        */
       for (int k = i*2+1; k<length; k = k*2+1){
           /*
           判斷該節點是否有右節點，即k+1是否超過數組範圍索引
           如果有，則比較大小，拿出最大值的節點
            */
           if (k+1 < length && array[k] < array[k+1]){
               //如果右節點大，把索引k+1即可使k指向右節點
               k++;
           }

           //判斷傳入的非葉子節點的值是否小於它子樹節點的最大值
           if (temp < array[k]){
               //如果小於則把大於它的子節點的值賦給該節點
               array[i] = array[k];
               //再把非葉子節點的指針指向該子節點的位置，繼續循環
               i = k;
           }else {
               /*
               因為在調整二叉樹數組成大頂堆數組時，是從下到上進行遍歷調整的，
               而循環條件是從上到下遞減的，所以當上訴條件不成立時直接退出即可
                */
               break;
           }
       }
       /*
       因為在上面節點和節點的交換中使用的是插入演算法，所以在退出循環時，
       需要將初始傳入的非葉子節點的值temp賦給最後一個實現交換(插入)的節點,即i指向的節點
        */
       array[i] = temp;
    }
}