public class HeapSort{

    public static void main(String[] args) {

        int arr[] = {1,4,2,3,6,7,8,9,10,4};
        for(int i=arr.length;i>0;i--){

            for(int j=i/2-1;j>=0;j--){ //从最大的非叶子节点开始
                adjustHeap(arr,j,i);
                swap(arr,0,i-1);
            }
        }

        //打印排序后的数组
        StringBuffer sb = new StringBuffer();
        for(int m=0;m<arr.length;m++){
            sb.append(arr[m]).append(",");
        }
        System.out.println(sb.toString());

    }

    //参数：i 数组的下标（0开始计数），len为当前参与排序的数组真实长度（1开始计数）
    public static void adjustHeap(int arr[], int i,int len){
        int temp = arr[i];
        for(int k=2*i+1;k<len;k=2*k+1){ //k=2*k+1，保证在当前节点未移动时，继续向下遍历
            //其中k=2*i+1为i节点的左子树，k=2*i+1为i节点的右子树
            if(k+1<len && arr[k]<arr[k+1]){
               k=k+1;

            }
            if(arr[k]>arr[i]){
                arr[i] = arr[k];
                i = k; //这个存值，是为了识别替换的位置，执行arr[i] = temp;
            }

        }
        arr[i] = temp;
    }

    public static void swap(int arr[],int start,int end){
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }
}