递归

    public static void heapSort(int[] data) {  
        int size = data.length;
        for (int i = 0; i < size; i++) {  
            createMaxdHeap(data, size - 1 - i);  
            swap(data, 0, size - 1 - i);  
        }  
    }  
  
    public static void createMaxdHeap(int[] data, int last) { 
        for(int i = (last-1)/2; i >= 0; i--){//找root节点
            int tmp = i;
            while(tmp * 2 + 1 <= last){
                int big = tmp * 2 + 1;
                if(big < last && data[big] < data[big+1]){//比较左孩子和右孩子，取较大的index
                    big++;
                }
                if(data[tmp] < data[big]){//把大的上升到root
                    swap(data,tmp,big);
                    tmp = big;
                }else{
                    break;
                }
            }
        }
    }  
    public static void swap(int[] data, int i,int j){
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    } 

非递归

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        // Write your code here
        // 堆
        heapSort(A);
    }
    
    static void heapSort( int[]a ){
        for(int n=a.length;n>0;n--){             
        //n,i均表示的是位置，不是数组下标；从整个堆开始，
            for(int i=n/2;i>0;i--){ 
            //比较父节点与子节点的值，将大的往上调
                if((2* i< n)&&( a[ i-1]< a[2* i])){ //满二叉树
                    swap(a,i-1,2*i); //  不能使用swap(a[i-1],a[2*i]），因为数组传递不过去，不能对数组元素值进行处理
                }
                if( a[ i-1]< a[2* i-1]){
                    swap(a,i-1,2*i-1);
                }
            }
            swap(a ,0,n -1);  //每次找到最大值存储在最末的位置
        }
    }
    public static void swap(int[] data, int i,int j){
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    } 
}