//本程序取自Clifford A.Shaffer著張銘等譯“數據結構與算法分析”第 171 頁，例8.6
//基于最大堆的堆排序問題解法
 //heapsort on minheap
 import java.io.*;
 class MinHeap 
   {                      //Min-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 MinHeap(int[] h,int num,int min)//constructor
     { Heap=h;n=num;size=min;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 MinHeap
  public class MinHeap1
 {
  static void heapsort(int array[])  //heapsort
    {
     MinHeap H=new MinHeap(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);
   }
}