package com.jiucaiyuan.net.algrithm.sort;



/**

 * <pre>

 * 堆排序

 *   数组表示二叉树[0,1,2,3,4,5,6]       下标i的左子节点是2*i+1 ，右子节点是 2*i+2  ， 父节点是 (i-1)/2

 * 	 大根堆：以i为头的整棵树，最大值是i

 * 	 小根对：以i为头的整棵树，最小值是i

 *   优先级队列结构就是堆结构

 * 	 时间复杂度O(N*logN)  空间复杂度O(1)

 * </pre>

 * Created by jiucaiyuan on 2022/3/31.

 */

public class Sort06_HeapSort {

    /**

     * 堆排序算法

     *

     * @param arr

     * @return

     */

    public static void heapSort(int[] arr) {

        if (arr == null || arr.length < 2) {

            return;

        }

        for (int i = 0; i < arr.length; i++) { //O(N)

            heapInsert(arr, i);  //O(logN)

        }



        //这个过程处理完，arr也成为大根堆

//        for (int i = arr.length; i > 0; i--) {

//            heapify(arr, i, arr.length);

//        }



        int heapSize = arr.length;

        while (heapSize > 0) {  //O(N)

            swap(arr, 0, --heapSize);     //O(logN)

            heapify(arr, 0, heapSize);  //O(1)

        }

    }



    /**

     * 指定index位置的数加入到arr[0~index-1]所表示的大根堆中

     *

     * @param arr

     * @param index

     */

    public static void heapInsert(int[] arr, int index) {

        //如果index位置的数比父节点数大

        while (arr[index] > arr[(index - 1) / 2]) {

            //当前数和父节点数交换

            swap(arr, index, (index - 1) / 2);

            //再判断和父节点大小

            index = (index - 1) / 2;

        }

    }



    /**

     * 指定index位置的数加入到arr[0~index-1]所表示的大根堆中

     *

     * @param arr

     * @param index

     */

    public static void heapify(int[] arr, int index, int heapSize) {

        int leftChild = 2 * index + 1;

        //如果节点有子节点

        while (leftChild < heapSize) {

            //选择较大的子节点下标

            int bigger = leftChild + 1 < heapSize && arr[leftChild] < arr[leftChild + 1]

                    ? leftChild + 1 : leftChild;

            //父和较大子节点较大的数的下标给bigger

            bigger = arr[index] > arr[bigger] ? index : bigger;

            //如果父就是较大的数，即不用再处理了

            if (index == bigger) {

                return;

            }

            //较大的数和当前数交换

            swap(arr, index, bigger);



            //下次继续判断当前数

            index = bigger;

            leftChild = 2 * index + 1;

        }

    }



    /**

     * @param arr

     * @param l

     * @param r

     */

    private static void swap(int[] arr, int l, int r) {

        int temp = arr[l];

        arr[l] = arr[r];

        arr[r] = temp;

    }



    public static void main(String[] args) {

        int[] arr = {12, 5, 3, 7, 3, 8, 4, 3, 2, 2, 6, 8, 6, 0, 9, 5, 3};

        heapSort(arr);

        print(arr);

    }



    private static void print(int[] arr) {

        if (arr == null) {

            return;

        }

        for (int a : arr) {

            System.out.print(a + "\t");

        }

        System.out.println();

    }

}