minheap.h

该程序用ＶＣ实现了一个小型文件压缩与解压缩功能的程序

#ifndef MinHeap_H
#define MinHeap_H
const int DefaultSize = 20;
#include<iostream.h>
#include<assert.h>

template<class T>
class MinHeap
{
	private:
		T* heap;
		int CurrentSize;
		int MaxHeapSize;
		void FilterDown(int i,int m);
		void FilterUp(int i);	
		friend ostream& operator << (ostream& os,const MinHeap<T>& p);
	public:
		MinHeap(int maxSize);
		MinHeap(T a[],int n);
		int Get(){return CurrentSize;}
		~MinHeap() {delete []heap;}
		const MinHeap<T>& operator = (const MinHeap<T>& p);
		int Insert(const T& x);
		int RemoveMin(T& x);
		int IsFull() const {return CurrentSize == MaxHeapSize;}
		int IsEmpty() const {CurrentSize == 0;}
		int MakeEmpty() {CurrentSize = 0;}

};

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

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

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

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

template<class T>
void MinHeap<T>::FilterUp(int Start)
{
	int j=Start,i=(Start-1)/2;
	T temp = heap[Start];
	while(j>0){
		if(heap[i] <= temp) break;
		else{
			heap[j] = heap[i];
			j=i;i=(j-1)/2;
		}
		heap[j] = temp;
	}
}

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

template<class T>
ostream& operator << (ostream& os,const MinHeap<T>& p)
{
	for(int i=0;i<p.CurrentSize;i++)
		os<<p.heap[i]<<" ";
	return os;
}
#endif