package com.lin.tree_0308;

import java.text.SimpleDateFormat;

import java.util.Arrays;

import java.util.Date;

public class HeapSort {

    public static void main(String[] args) {

//        int[] arr = {4, 6, 8, 5, 9};

        // 随机生成

        int[] arr = new int[80000000];

        for(int i = 0; i < 80000000; i++) {

            arr[i] =(int)(Math.random()*8000000);

        }

        Date date1 = new Date();

        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");

        String format1 = simpleDateFormat.format(date1);

        System.out.println("排序前时间为：" + format1);

        heapSort(arr);

        Date date2 = new Date();

        String format2= simpleDateFormat.format(date2);

        System.out.println("排序后时间为：" + format2);

    }

    // heapSort

    public static void heapSort(int[] arr) {

        int temp = 0;

//        adjustHeap(arr, 1, arr.length);

//        System.out.println("第一次：" + Arrays.toString(arr));

//

//        adjustHeap(arr, 0, arr.length);

//        System.out.println("第二次：" + Arrays.toString(arr));

        // 将无序序列建成一个堆，根据升序需求选择大顶堆或小顶堆

        for(int j = arr.length/2 -1; j >= 0; j--) {

            adjustHeap(arr, j, arr.length);

        }

        // 将堆顶元素与尾元素交换，将最大元素沉到数组尾端

        // 重新调整至堆，继续交换，反复操作直至整个序列有序

        for(int j = arr.length-1; j > 0; j--) {

            temp = arr[j];

            arr[j] = arr[0];

            arr[0] = temp;

            adjustHeap(arr, 0, j);

        }

    }

    // heap

    /**

     *

     * @Description:

     * @author LinZM

     * @date 2021-3-11 10:14:16

     * @version V1.8

     * @param arr 待调整数组

     * @param i 表示非叶子节点在数组中的索引

     * @param lenght 表示对多少个元素继续调整，逐渐变小

     */

    public static void adjustHeap(int[] arr, int i, int length) {

        // 先取出当前元素的值

        int temp = arr[i];

        // j = 2 * i + 1 j是i节点的左节点

        for(int j = i * 2 + 1; j < length; j = j * 2 + 1) {

            if(j+1 < length && arr[j] < arr[j+1]) {//右子节点大于左子节点

                j++;// j指向有子节点

            }

            if(arr[j] > temp) {// 子节点大于父节点

                arr[i] = arr[j];

                i = j;

            } else {

                break;

            }

        }

        arr[i] = temp;

    }

}