public class HeapSort {

    public static void main(String[] args) throws Exception{
        Integer [] a  = new Integer[]{32,12,345,5,66,23};
        heapSort(a);

        Arrays.stream(a).forEach(System.out::println);
    }

    /**
     * Internal method for heapSort that is used in  deleteMax and buiildHeap
     * @param i the position from which to percolate down
     * @param n the binary size of the binary heap
     */
    public static void percDown(Integer[] a,int i, int n){
        int child;
        int temp;

        for(temp= a[i]; leftChild(i) < n; i = child){
            child = leftChild(i);

            if(child != n-1  && a[child] < a[child+1])
                child++;

            if(temp < a[child])
                a[i] = a[child];
            else
                break;
        }
         a[i] = temp;
    }


    private static int leftChild(int i){
        return 2 * i + 1;
    }

    public static void heapSort(Integer[] a){

        /**初始化堆的时候是对所有的非叶子结点进行筛选。
        最后一个非终端元素的下标是[n/2]向下取整，所以筛选只需要从第[n/2]向下取整个元素开始，从后往前进行调整。
         */
        for(int i = a.length/2-1; i>=0; i--){ //buildHeap
            percDown(a,i,a.length);
        }

        for(int i=a.length-1; i > 0; i--){
            swapReferences(a,0,i);  //deleteMax
            percDown(a,0,i);
        }
    }

    //deleteMax
    public static void swapReferences(Integer[] a, int i, int n){
        Integer temp=a[i];
        a[i] = a[n];
        a[n] = temp;
    }

}