package sort.choose;

import java.util.Arrays;

/**
 * @author chenyi
 * @Description 二叉樹遍歷
 * @date 2022/2/17 15:30
 */
public class HeapSort {

    public static void main(String[] args) {
        //int arr[] = {4,6,8,5,9};
        int arr[] = {10, 6, 14, 4, 8, 12, 16, -1, 1, 99};
        System.out.println("遍歷順序存儲二叉樹");
        System.out.println(Arrays.toString(arr));
        /*System.out.println("第一次堆排序");
        adjustHeap(arr,arr.length/2-1,arr.length);
        System.out.println(Arrays.toString(arr));
        System.out.println("第二次堆排序");
        adjustHeap(arr,1,arr.length);
        System.out.println(Arrays.toString(arr));
        System.out.println("第三次堆排序");
        adjustHeap(arr,0,arr.length);
        System.out.println(Arrays.toString(arr));*/
        System.out.println("堆排序");
        for (int i = (arr.length >> 1) - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        for (int i = arr.length - 1; i > 0; i--) {
            // 把最大的數放到末尾
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            adjustHeap(arr, 0, i);
        }
        System.out.println(Arrays.toString(arr));

    }

    private static void adjustHeap(int[] arr, int i, int length) {
        // 記錄i的值
        int temp = arr[i];
        int max = i;
        // 至少要有一個左節(jié)點吧
        while (max * 2 < length - 1) {
            // 比較樹的左右節(jié)點
            if (arr[2 * i + 1] > arr[max]) {
                max = 2 * i + 1;
            }
            if (2 * i + 2 < length && arr[2 * i + 2] > arr[max]) {
                max = 2 * i + 2;
            }
            if (max == i) {
                break;
            }
            // 交換之后要考慮是否會影響子樹，所以要對變更的節(jié)點進行再次調整
            arr[i] = arr[max];
            arr[max] = temp;
            i = max;
        }
    }


}