//本程序取自Clifford A.Shaffer著張銘等譯“數據結構與算法分析”第 171 頁，例8.6
//基于最大堆的堆排序問題解法
 //heapsort on maxheap
  import java.io.*;
 
 class MaxHeap 
   {                       //Max-heap impmentation
     private int[] Heap;   //Pointer to the heap array
     private int size;     //Maximum size of the heap
     private int n;        //Number of intents now in heapheapsoet
    public MaxHeap(int[] h,int num,int max)//constructor
     { Heap=h;n=num;size=max;buildheap();}
    public int heapsize()    //return current size of the heap
     {  return n;}
    public boolean isLeaf(int pos)//true if pos is a leaf position
     { return(pos>=n/2)&&(pos<n);} 
    public static void Assert_notFalse(boolean p,String q)
     { if(!p)System.out.println((String)q);}
    public static int key( int [] q,int p)
     {  return q[p];}
  //return position for left child of pos
    public int leftchild(int pos)
     { Assert_notFalse(pos<n/2,"position has no left child");
     return 2*pos+1;
     }
  //return position for right child of pos
    public int rightchild(int pos)
     {Assert_notFalse(pos<(n-1)/2,"position has no right child");
      return 2*pos+2;
     }
    public int parent(int pos)//return position for parent
   {Assert_notFalse(pos>0,"position has no parent");
     return (pos-1)/2;
   }
  public void buildheap() //Heapify contents of Heap
   {  for(int i=n/2-1;i>=0;i--)siftdown(i);}
  public static void swap(int[] q,int i,int j)
   {
    int temp;
    temp=q[i];q[i]=q[j];q[j]=temp;
   }
  private void siftdown(int pos) //put intent in itscorrent place
   {Assert_notFalse((pos>=0)&&(pos<n),"illegal heap position ");
     while(! isLeaf(pos))
      {
       int j=leftchild(pos);
       if((j<(n-1))&&(key(Heap,j)<key(Heap,j+1)))
         j++;// j is now index of child with greater value
       if(key(Heap,pos)>=key(Heap,j)) return;// Done
       swap(Heap,pos,j);
       pos=j;//Move down 
      }
   }
  public void insert(int val) //Insert value into heap
   {
     Assert_notFalse(n<size,"Heap is full ");
     int curr=n++;
     Heap[curr]=val;      //start t end of heap
     //Now sift up until curr's parent's key>curr's key
     while((curr!=0)&&(key(Heap,curr)>key(Heap,parent(curr))))
     {
      swap(Heap,curr,parent(curr));
       curr=parent(curr);
     }
   }
  public int removemax()  //remove maximum value
    {
     Assert_notFalse(n>0,"Removing from empty heap ");
     swap(Heap,0,--n);//swap maximum with last value
     if(n!=0)         //Not on last intent
       siftdown(0);   //Put new heap root val in corrent place 
     return Heap[n];
    }
  //Remove intent at specified position 
  public int remove(int pos)
    {
    Assert_notFalse((pos>0)&&(pos<n),"illegal heap position ");
    swap(Heap,pos,--n);//swap with last value
    if(n!=0)     //Not on last intent
     siftdown(pos);//put new heap root val in corrent place
    return Heap[n];
   }
  public void outmaxheap()
   {
     for(int i=0;i<=n-1;i++)
     System.out.print(Heap[i]+"  ");
     System.out.println(); 
   }  
     
 }  // class MaxHeap
  public class MaxHeap1
 {
  
  static void heapsort(int array[])  //heapsort
    {
     MaxHeap H=new MaxHeap(array,array.length,array.length);
     System.out.println("建最大堆之后");
     H.outmaxheap();
     for(int i=0;i<array.length;i++) //now sort
     H.removemax(); //removemax places max value at end of heap
    } 
  static void outarray(int array[])//  output a array
    {
       for(int i=0;i<=array.length-1;i++)
       System.out.print(array[i]+"  ");
       System.out.println();
    }

  public static void main(String args[])
   { 
     int m1=7;int n1=25;
     int a[]={1,8,3,6,5,4,7};
     System.out.println("堆排序之前");
     outarray(a);
    heapsort(a);
     System.out.println("堆排序之后");
     outarray(a);
   }
}