minheap1_1.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自Clifford A.Shaffer著张铭等译“数据结构与算法分析”第 171 页，例8.6
//基于最小堆的堆排序问题解法
 //heapsort on minheap
 import java.io.*;
class MinHeap 
   {                      //Min-heap impmentation
     static int[] Heap;  //Pointer to the heap array
     static int size;     //Maximum size of the heap
     static int n;        //Number of intents now in heapheapsoet
    public MinHeap(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 static 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 static 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 static int rightchild(int pos)
     {Assert_notFalse(pos<(n-1)/2,"position has no right child");
     return 2*pos+2;
     }
    public static int parent(int pos)//return position for parent
     {Assert_notFalse(pos>0,"position has no parent");
     return (pos-1)/2;
     }
    public static  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 static 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 static 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 static int removemin()  //remove minimum value
      {
       Assert_notFalse(n>0,"Removing from empty heap ");
       swap(Heap,0,--n);//swap minimum 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 static 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 static void outMinHeap()
     {
     for(int i=0;i<=n-1;i++)
     System.out.print(Heap[i]+"  ");
     System.out.println(); 
     }       

  static void heapsort()  //heapsort
    {
     System.out.println("建最小堆之后排序");
     
     for(int i=1;i<size-1;i++) //now sort
     System.out.print(removemin()+"  ");
     System.out.println( );    //removemin places min value at end of heap
    } 
 }// class MinHeap
  public class MinHeap1_1
 {
  public static void main(String args[])
   { 
     int m1=0;int n1=7;
     int a[]={8,1,3,6,5,4,7};
     MinHeap abc=new MinHeap(a,m1,3);
     System.out.println("初始堆");
    // abc.outMinHeap();
     for(int i=0;i<=2;i++)
       {
         int x1=a[i];
         abc.insert(x1);       
       }
     System.out.println("0堆");
     abc.outMinHeap();
     for(int i=3;i<n1;i++)
       {
         int x=abc.removemin(); 
         System.out.println("移出x="+x);
         x=x+a[i];
         abc.insert(x);
       }
        abc.outMinHeap(); 
   }
}