minheap.h

在win32下的文本huffman压缩以及文本的解压。

#ifndef MINHEAP_H
#define MINHEAP_H

const int DefaultSizeofHeap=20;

template<class Type>
class MinHeap  //最小堆
{
public:
	MinHeap(int maxSize);
	MinHeap(Type arr[],int n);  //利用数组来构建最小堆
	~MinHeap();
	void operator=(const MinHeap &sc);
	bool Insert(Type *x);  //往堆中插入一个元素  
	Type* RemoveMin();  //从堆顶删除一个元素
	bool IsEmpty();
	bool IsFull();
	void MakeEmpty();   //置空
private:
	void FilterDown(int start,int end);  //从上向下梳理
	void FilterUp(int m);  //从下向上梳理

	Type* heap;  //堆为数组结构
	int current;  //堆最后一个元素的下标
	int MaxHeapSize;  //堆的最大容量
	bool isRef;  //标志:堆的元素是否和外部共享
};
template<class Type>
MinHeap<Type>::~MinHeap()
{
	if(!isRef)
		delete[] heap;
}
template<class Type>
bool MinHeap<Type>::IsEmpty()  //返回是否堆空
{
	return current==-1;
}
template<class Type>
bool MinHeap<Type>::IsFull()  //返回是否堆满
{
	return current==MaxHeapSize-1;
}
template<class Type>
void MinHeap<Type>::MakeEmpty()  //重置堆
{
	current=-1;
}
template<class Type>
Type* MinHeap<Type>::RemoveMin()  //删除堆顶,并将该指针返回
{
	if(IsEmpty())
	{
		cout<<"Heap Empty!"<<endl;
		return NULL;
	}
	Type temp=heap[0];
	heap[0]=heap[current];
	heap[current]=temp;
	current--;
	FilterDown(0,current);
	Type *temp1=new Type;
	*temp1=temp;
	return temp1;
}
template<class Type>
bool MinHeap<Type>::Insert(Type *x)  //将元素x插入堆
{
	if(IsFull())
	{
		cout<<"Heap Full!"<<endl;
		return false;
	}
	current++;
	heap[current]=*x;
	FilterUp(current);
	return true;
}
template<class Type>
void MinHeap<Type>::operator=(const MinHeap &sc)  //复制堆
{
	current=sc.current;
	MaxHeapSize=sc.MaxHeapSize;
	if(!isRef)
		delete[] heap;
	isRef=false;
	heap=new Type[MaxHeapSize];
	for(int i=0;i<=current;i++)
		heap[i]=sc.heap[i];
}

template<class Type>
MinHeap<Type>::MinHeap(int maxSize)
{
	MaxHeapSize=maxSize>DefaultSizeofHeap?maxSize:DefaultSizeofHeap;
	heap=new Type[MaxHeapSize];
	isRef=false;
	current=-1;
}

template<class Type>
MinHeap<Type>::MinHeap(Type arr[], int n)
{
	MaxHeapSize=n>DefaultSizeofHeap?n:DefaultSizeofHeap;
	current=n-1;
	heap=arr;
	isRef=true;
	int currentPos=(current-2)/2;
	while(currentPos>=0)
	{
		FilterDown(currentPos,current);
		currentPos--;
	}
}
template<class Type>
void MinHeap<Type>::FilterUp(int m)  //从下到上梳理
{
	int i=(m-2)/2,j=m;
	Type temp=heap[m]; 
	while(j>0)  //不断地和其父母结点比较,直至父母结点较小或者已到顶
	{
		if(temp.getKey()>=heap[i].getKey())
			break;
		else
		{
			heap[j]=heap[i];
			j=i;
			i=(i-2)/2;
		}
	}
	heap[j]=temp;
}
template<class Type>
void MinHeap<Type>::FilterDown(int start,int end)  //从上到下梳理
{
	int i=start,j=2*i+1;
	Type temp=heap[i];
	while(j<=end)  //不断地和其子女比较,直至已到end位置或者小于其子女
	{
		if(j<end)
			if(heap[j].getKey()>heap[j+1].getKey())
				j++;
		if(temp.getKey()<=heap[j].getKey())
			break;
		else
		{
			heap[i]=heap[j];
			i=j;
			j=2*j+1;
		}
	}
	heap[i]=temp;
}
#endif