huffman.~h

用加权二叉树

 typedef  char ElemType ;
typedef struct node {
	ElemType data;
	struct node *lchild;
	struct node *rchild;
} Btree;

Btree * maketree(Btree * First, Btree * Second){
        Btree * merger=NULL;
        merger->data=First->data+Second->data;
        merger->lchild=First;merger->rchild=Second;
        }



  template<class Type> class MinHeap{
  public :
   MinHeap(int );           // 建立空堆
   MinHeap(Type arr[],int n); //建立以arr[]为元素的堆
   ~MinHeap(){delete []heap;};
   int Insert(Type &x);
   int RemoveMin(Type &x);   //删除堆顶元素

   int IsEmpty()const {return CurrentSize == 0;}
   int IsFull() const {return CurrentSize == MaxHeapSize;}
    void zzzz()const {cout<<heap[0]<<heap[1]<<heap[2]<<heap[3]<<heap[4]<<heap[5];
                         cout<<heap[6]<<heap[7];}
   private:
   enum {DefaultSize = 10};
   Type *heap;                      //存放最小堆中元素的数组!
   int CurrentSize;                 //当前堆中元素的个数
   int MaxHeapSize;                 //允许存放最多个数
   void FilterDown(int i,int m);    //自顶向下调整
   void FilterUp(int i);    //从底向上调整
   };

   template<class Type>  MinHeap<Type> :: MinHeap(int maxSize){
    MaxHeapSize = DefaultSize< maxSize ? maxSize : DefaultSize;
    heap=new Type[MaxHeapSize];
    CurrentSize = 0;
    } ;

    template<class Type>  MinHeap<Type> :: MinHeap(Type arr[],int n){
     MaxHeapSize = DefaultSize< n ? n : DefaultSize;
     heap=new Type[MaxHeapSize];
     heap=arr; CurrentSize = n;
     int currentPos = ( CurrentSize - 2)/2;
     while (currentPos>=0){
         FilterDown(currentPos,CurrentSize - 1);
         currentPos --;
         }
  }  ;

  template<class Type> void MinHeap<Type> :: FilterDown(const int start,const int End){
   int i=start,j=2*i+1;Type temp=heap[i];
   while(j <= End){
     if(j < End&&heap[j]>heap[j+1])j++;
     if(temp<=heap[j])break;
     else{heap[i]=heap[j]; i=j; j=2*j+1;}
      }
      heap[i]=temp;
   };

  template<class Type> void MinHeap<Type> :: FilterUp(const int start){

    int j=start,i=(j-1)/2;Type temp = heap[j];

    while(j>0) {
       if(heap[j]>=heap[i])break;
       else{ heap[j]=heap[i]; heap[i]= temp; j=i;i=(j-1)/2;}
       }
    };

  template<class Type> int  MinHeap<Type> :: Insert( Type &x){
        if(CurrentSize=MaxHeapSize) {cerr << "Heap full"<<endl;return 0}
        heap[CurrentSize]=x; FilterUp(CurrentSize);
        CurrentSize++;
        return 1;
  };

  template <class Type> int MinHeap<Type> :: RemoveMin(Type &x){
  if(!CurrentSize){cout<<"Heap empty"<<endl;return 0;}
  x=heap[0]; heap[0]=heap[CurrentSize-1];
  CurrentSize--;
  FilterDown(0,CurrentSize - 1);
  return 1;
  };