heap.h

用VC语言实现HAUFMM的编码

#ifndef Heap_h
#define Heap_h
#include<stdlib.h>
#include<iostream.h>
template<class Type> class MinPQ{
	public:
		virtual int Insert(const Type &)=0;
		virtual int RemoveMin(Type &)=0;
};
template<class Type> class MinHeap:public MinPQ<Type>{
		public:
		MinHeap(int=256);
		MinHeap(Type arr[],int n);
		~MinHeap(){}//delete []heap;
	    MinHeap(const MinHeap<Type> & R);
		const MinHeap<Type>& operator=(const MinHeap<Type> & R);
		int Insert(const Type &x);
		int RemoveMin(Type &x);
		int IsEmpty()const{return CurrentSize==MaxHeapSize;}
		void MakeEmpty(){CurrentSize=0;}
	private:
		enum{DefaultSize=256};
		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(const MinHeap<Type> & R){
	MaxHeapSize=DefaultSize<R.MaxHeapSize?R.MaxHeapSize:DefaultSize;
	heap=new Type[MaxHeapSize];
	CurrentSize=R.CurrentSize;
	heap=R.heap;
}
template<class Type> const MinHeap<Type>& MinHeap<Type>::operator=(const MinHeap<Type> & R){
	MaxHeapSize=DefaultSize<R.MaxHeapSize?R.MaxHeapSize:DefaultSize;
	heap=new Type[MaxHeapSize];
	CurrentSize=R.CurrentSize;
	heap=R.heap;
	return *this;
}
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 EndOfHeap){
	int i=start,j=2*i+1;Type temp=heap[i];
	while(j<=EndOfHeap){
		if(j<EndOfHeap&&heap[j].key>heap[j+1].key)j++;
		if(temp.key<=heap[j].key)break;
		else{heap[i]=heap[j];i=j;j=2*j+1;}
	}
	heap[i]=temp;
}
template<class Type> void MinHeap<Type>::FilterUp(int start){
	int j=start,i=(j-1)/2;Type temp=heap[j];
	while(j>0){
		if(heap[i].key<=temp.key)break;
		else{heap[j]=heap[i];j=i;i=(i-1)/2;}
	}
	heap[j]=temp;
}
template<class Type> int MinHeap<Type>::Insert(const Type &x){
	if(CurrentSize==MaxHeapSize){cerr<<"Heap Full"<<endl;exit(1);}
	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;
}
#endif