package sort;

public class  HeapSort{

    public static void main(String[] args)

    {

        new HeapSort().run();

    }

    public void run(){

         int [] a={,,,,,};

        int len=a.length;

        /**

         * 循环建堆

         */

        for(int i=;i<len-;i++){

            /**

             * 建堆，建一次最大堆，寻到一个待排序序列的最大数

             */

            buildMaxHeap(a,len--i);

            /**

             * 交换堆顶（待排序序列最大数）和最后一个元素

             */

            swap(a,,len--i);

        }  

        for(int j=;j<len;j++){

            System.out.print(a[j]+" ");

        }

    }

    /**

     * 对数组 从0到lastIndex建大顶堆

     */

    public void buildMaxHeap(int[] arr, int lastIndex){

         /**

          * 从最后一个节点（lastIndex）的父节点开始

          */

        for(int i=(lastIndex-)/;i>=;i--){

            /**

             * k保存正在判断的节点

             */

            int k=i;

            /**

             * 如果当前k节点的子节点存在

             */

            while(k*+<=lastIndex){

                /**

                 * k节点的左子节点的索引

                 */

                int biggerIndex=*k+;

                /**

                 * 如果k节点的左子节点biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在

                 */

                if(biggerIndex<lastIndex){

                    /**

                     * 若果右子节点的值较大

                     */

                    if(arr[biggerIndex]<arr[biggerIndex+]){

                        /**

                         * biggerIndex总是记录较大子节点的索引

                         */

                        biggerIndex++;

                    }

                }

                /**

                 * 如果k节点的值小于其较大的子节点的值 ，交换他们

                 */

                if(arr[k]<arr[biggerIndex]){

                    swap(arr,k,biggerIndex);

                    /**

                     * 将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值

                     */

                    k=biggerIndex;

                }else{

                    /**

                     * 当前判断结点k（父结点），大于他的两个子节点时，跳出while循环

                     */

                    break;

                }

            }

        }

    }

    /**

     * 交换下标为i、j的两个元素

     */

    private void swap(int[] data, int i, int j) {

        int tmp=data[i];

        data[i]=data[j];

        data[j]=tmp;

    }

}