fac4_4.java

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

//
//本程序取自王晓东编著“算法分析与设计”第 117 页，例
//构造哈夫曼编码问题贪心(dijksra)解法
  
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
    class Huffman implements Comparable
      {
      Bintree tree;
      float weight;
      
      private Huffman(Bintree tt,float ww)
        {
           tree=tt;
           weight=ww;
        }
     public int compatrTo(Object x)
       {
       float xw=((Huffman)x).weight;
       if(weight<xw)return -1;
       if(weight==xw)return 0;
       return 1;
       }
     }
    public class Fac4_4{
    public static Bintree huffmanTree(float[] f)
     {
      int n=f.length;
      Huffman[] w=new Huffman[n+1];
      Bintree zero=new Bintree();
      for(int i=0;i<n;i++)
      {
        Bintree x=new Bintree();
        x.makeTree(new MyInteger(i),zero,zero);
        w[i+1]=new Huffman(x,f[i]);
      }
    // 
     MinHeap H=new MinHeap(  );
     H.initialize(w,n);
    //
      for(int i=1;i<n;i++)
      {
       Huffman x=(Huffman).H.removemin();
       Huffman y=(Huffman).H.removemin();
       Bintree z=new Bintree();
       z.makeTree(null,x.tree,y.tree);
       Huffman t=new Huffman(z,x.weight+y.weight);
       H.Put(t);
      }
    return ((Huffman)H.removemin()).tree;
    }

    public static void main(String argc[])
      {
      
      System.out.println("");
      }
   }