package com.rao.linkList;

import java.util.Arrays;

/**

 * @author Srao

 * @className HeapSort

 * @date 2019/12/3 15:29

 * @package com.rao.linkList

 * @Description： 堆排序

 */

public class HeapSort {

    /**

     * 在二叉堆当中，一般是删除根元素，在删除根元素之后，把最后一个元素当作根元素，然后进行下沉

     * @param arr

     * @param parent：被当作根元素的节点，从这个元素开始下沉

     * @param length：数组的长度

     * @return

     */

    public static int[] downAdjust(int[] arr, int parent, int length){

        //获取临时的根节点

        int temp = arr[parent];

        //计算左孩子节点

        int child = parent*2+1;

        //进行下沉操作

        while (child < length){

            //先对比左右孩子的大小，用小的那一个进行操作

            if (child+1 < length && arr[child+1] < arr[child]){

                child++;

            }

            //如果父节点比子节点小，就直接退出

            if (temp <= arr[child]){

                break;

            }else {//如果父节点比子节点大，就把子节点赋值给父节点

                arr[parent] = arr[child];

                //让父节点指针指向子节点

                parent = child;

                child = parent*2+1;

            }

        }

        arr[parent] = temp;

        return arr;

    }

    /**

     * 进行堆排序,因为二叉堆的顶部的数一定是最小的，

     * 所以把堆顶元素和堆的最后一个元素交换，然后重新构成一个二叉堆，

     * 每次都把最小的元素放在堆的最后

     * @param arr

     * @return

     */

    public static int[] sort(int[] arr, int length){

        //先构建一个二叉堆

        for (int i = (length-1)/2; i>=0; i--){

            downAdjust(arr, i, length);

        }

        //进行排序

        for (int i = length-1; i > 0; i--){

            //先把最小的元素放在堆的最后面，然后对堆的其它元素进行下沉

            int temp = arr[0];

            arr[0] = arr[i];

            arr[i] = temp;

            downAdjust(arr, 0, i);

        }

        return arr;

    }

    public static void main(String[] args) {

        int[] arr = new int[]{1, 3, 2, 6, 5, 0};

        System.out.println(Arrays.toString(arr));

        sort(arr, arr.length);

        System.out.println(Arrays.toString(arr));

    }

}