堆排序

public class HeapSort   
{   
    int [] a = {3,1,5,2,4,9,8,7,6,4};   
    //数组的索引以0开始 ID也是从0开始   
    //父节点的索引   
       
    public int parentID(int childID)   
    {   
        return (childID-1)/2;   
        }   
       
    //左孩子的索引   
    public int leftChildID(int parentID)   
    {   
        return parentID*2+1;   
        }   
     /*
        创建大顶堆,将数组初始为一个大顶堆
     */
    public void creatMaxHeap()   
    {   
        int lastID = a.length-1;   
        for(int i = parentID(lastID); i >= 0 ; i--)   
                {    
             int k=i;   
        while(leftChildID(k) <= lastID)   
        {   
        int j = leftChildID(k);   
                   if(j < lastID)   //如果有两个孩子
    {   
            if(a[j] < a[j+1])   //选大的那个孩子
                  {   
        j++;   
        }   
             }   
          if(a[k] < a[j])   如果父结点比孩子小
                                {   
                                    int temp = a[k];   
                                    a[k] = a[j];   
                                    a[j] = temp;   
                                    k=j;   
                                    }   
                                    else break;                        
                            }   
                }   
    }   
     //调整大顶堆 
    public void maintainHeap(int lastID)   
    {   
        int k=0;   
         while(k <= parentID(lastID))   
            {   
                int j = leftChildID(k);   
                if( j < lastID)   
                {   
                    if(a[j] <= a[j+1])   
                            j++;   
                       
                    }   
                    if( a[k] <a[j] )   
                    {   
                        int temp = a[j];   
                        a[j] = a[k];   
                        a[k] = temp ;   
                        k = j;   
                        }   
                        else break;   
                        }   
    }   
           
    public void heapSort()   
    {   
        creatMaxHeap();   
        int lastID = a.length-1;   
        while(lastID > 0)   
        {   
            int temp = a[lastID];   
            a[lastID] = a[0];   
            a[0] = temp;   
            lastID--;   
            if(lastID > 0)   
                        maintainHeap(lastID);   
               
            }   
           
        }   
       
    public void printA()   
    {   
        for(int i = 0; i< a.length; i++)   
            {   
                System.out.println(a[i]);   
                }   
        }   
    public static void main(String args[])   
    {   
        HeapSort hs = new HeapSort();   
        hs.heapSort();   
        hs.printA();   
        }   
           
  
}