public static int left(int i)  
{  
    return i * 2 + 1;  
}  
public static int right(int i)  
{  
    return i * 2 + 2;  
}  

void HeapSort(int a[],int n)//堆排序，输入的序列是数组。输入的数组转换为二叉树是按二叉树从上到下从左到右进行摆放的。
{
    int t,i;
    int j;
　　//将无序的数组构成最大堆
    for(i=n/2-1;i>=0;i--)    //最后一个非叶节点是n/2-1，从最后一个非也节点开始使得根大于叶子节点 
        HeapAdjust(a, i, n); //第i个节点为根节点是最大堆，但是还没有按照从小到大排好序。


    for(i=n-1;i>0;i--)
    {
        t=a[0];
        a[0] =a[i];
        a[i] =t;   //最大堆构建完成之后，元素0就是最大的，取出来放在最后，这样最大的元素下沉了，然后把前面n-1个元素调整为最大堆，把前面n-1个元素最大的移到倒数第二个位置，就是把第二个元素下沉了，一次类推。
        HeapAdjust(a,0,i);    
    }  
}

//以s为根节点的二叉树调整为最大堆
void HeapAdjust(int a[],int s,int n)
{
    int j,t;
    while(2*s+1<n) //有左节点就有右节点 ，是否有左右节点，
    {
        j=2*s+1 ;//指向左节点
        if((j+1)<n)//存在右节点
        {            
            if(a[j]<a[j+1])//右左子树小于右子树，则需要比较右子树
                j++; //序号增加1，指向右子树 
        }
        if(a[s]<a[j])//比较s与j为序号的数据
        {            
            t=a[s];  //交换数据 
            a[s]=a[j];
            a[j]=t;            
            s=j ;//堆被破坏，需要重新调整（如果s是中间节点，s,j交换位置之后，以j为根节点的二叉树有可能现在不满足最大堆），要保证是最大堆。后面利用到第一层最大，第二层第23大这个规律，

        } else //比较左右孩子均大则堆未破坏，不再需要调整 
　　　　     break; 
　 } 
}

public static void main(String[] args) {
        int[] a = new int[] {3,5,8,1,80,7,31,9,12,54,89};
        HeapSort(a,a.length);
    }

for (int i = 0; i < arrays.length; i++) {

        //每次建堆就可以排除一个元素了
        maxHeapify(arrays, arrays.length - i);

        //交换
        int temp = arrays[0];
        arrays[0] = arrays[(arrays.length - 1) - i];
        arrays[(arrays.length - 1) - i] = temp;

    }

/**
     * 完成一次建堆，最大值在堆的顶部(根节点)
     */
    public static void maxHeapify(int[] arrays, int size) {

        // 从数组的尾部开始，直到第一个元素(角标为0)
        for (int i = size - 1; i >= 0; i--) {
            heapify(arrays, i, size);
        }

    }

/**
     * 建堆
     *
     * @param arrays          看作是完全二叉树
     * @param currentRootNode 当前父节点位置
     * @param size            节点总数
     */
    public static void heapify(int[] arrays, int currentRootNode, int size) {

        if (currentRootNode < size) {
            //左子树和右字数的位置
            int left = 2 * currentRootNode + 1;
            int right = 2 * currentRootNode + 2;

            //把当前父节点位置看成是最大的
            int max = currentRootNode;

            if (left < size) {
                //如果比当前根元素要大，记录它的位置
                if (arrays[max] < arrays[left]) {
                    max = left;
                }
            }
            if (right < size) {
                //如果比当前根元素要大，记录它的位置
                if (arrays[max] < arrays[right]) {
                    max = right;
                }
            }
            //如果最大的不是根元素位置，那么就交换
            if (max != currentRootNode) {
                int temp = arrays[max];
                arrays[max] = arrays[currentRootNode];
                arrays[currentRootNode] = temp;

                //继续比较，直到完成一次建堆
                heapify(arrays, max, size);
            }
        }
    }