import java.util.Arrays;
import java.util.Random;

public class HeadSort {
    
    public static void main(String[] args) {
        //測試程式碼
        int[] arr = new int[20];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt() % 1000;
        }
        System.out.println(Arrays.toString(arr));
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static int[] heapSort(int[] arr) {

        // 構建最大堆
        buildHead(arr);

        // 每次將堆頂節點移到數組尾部，調整堆大小
        for (int i = 0; i < arr.length; i++) {

            // 即將要被堆刪除的節點序號
            int last = arr.length - i - 1;

            swap(arr, 0, last);

            // 改變傳遞的len參數表示堆將節點刪除
            heapify1(arr, 0, last);
        }
        return arr;
    }
    
    public static void buildHead(int[] arr) {
        int len = arr.length;
        //在滿二叉樹中，葉子節點數量是非葉子節點的2倍+1
        //第n-1層的最後一個節點就是len/2
        for (int i = len / 2; i >= 0; i--) {
            heapify1(arr, i, len);
        }
    }
    
    //遞歸下沉方式
    public static void heapify1(int[] arr, int parentIndex, int len) {
        // 左右孩子節點
        int left = 2 * parentIndex + 1;
        int right = 2 * parentIndex + 2;
        // 該父節點沒有左孩子
        if (left >= len) {
            return;
        }
        int latest = left;
        /*
        將節點進行下沉，如果進行了交換，還得繼續下沉，一直到成為葉子節點
         */
        // 得出左右孩子中的最大值
        if (right < len && arr[right] > arr[left]) {
            latest = right;
        }
        if (arr[latest] > arr[parentIndex]) {
            swap(arr, parentIndex, latest);
            heapify1(arr, latest, len);
        }
    }

    //循環下沉方式
    public static void heapify2(int[] arr, int parentIndex, int len) {

        //先將父節點值保存下來，跟左右的孩子比較，如果大於，跳出循環，如果小於，進行交換
        //交換之後節點繼續下沉，一直到成為葉子節點
        int tmp = arr[parentIndex];
        int children = 2 * parentIndex + 1;
        while (children < len) {

            // 左孩子大於右孩子，用左孩子的值與父節點比較
            if (children + 1 < len && arr[children + 1] > arr[children]) {
                children++;
            }

            /*
            父節點大於孩子的值，不用交換
            使用的是tmp，而不是arr[parentIndex]，因為一直是單向賦值，沒有交換
            直到確認tmp屬於哪個節點，在循環外面將tmp賦值
             */
            if (tmp >= arr[children]) {
                break;
            }

            // 將孩子節點的值賦給父節點，孩子節點暫時不變
            arr[parentIndex] = arr[children];
            parentIndex = children;
            children = children * 2 + 1;

        }
        arr[parentIndex] = tmp;
    }

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