www.pudn.com > compressor.zip > MinHeap.h

#ifndef MinHeap_H 
#define MinHeap_H 
const int DefaultSize = 20; 
#include 
#include 
 
template 
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& p); 
	public: 
		MinHeap(int maxSize); 
		MinHeap(T a[],int n); 
		int Get(){return CurrentSize;} 
		~MinHeap() {delete []heap;} 
		const MinHeap& operator = (const MinHeap& 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 
MinHeap::MinHeap(int maxSize) 
{ 
	MaxHeapSize = maxSize > DefaultSize ? maxSize : DefaultSize; 
	heap = new T[MaxHeapSize]; 
	assert(heap!=NULL); 
	CurrentSize = 0; 
} 
 
template 
MinHeap::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 
int MinHeap::Insert(const T& x) 
{ 
	if(CurrentSize == MaxHeapSize){ 
		cerr<<"Heap Full"< 
void MinHeap::FilterDown(const int Start,const int EndOfHeap) 
{ 
	int i=Start,j=2*Start+1; 
	T temp = heap[i]; 
	while(j<=EndOfHeap){ 
		if(jheap[j+1]) j++; 
		if(temp <= heap[j]) break; 
		else{ 
			heap[i] = heap[j]; 
			i=j;j=2*i+1; 
		} 
	} 
	heap[i] = temp; 
} 
 
template 
void MinHeap::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 
int MinHeap::RemoveMin(T& x) 
{ 
	if(!CurrentSize){ 
		cerr<<"Heap Empty"< 
ostream& operator << (ostream& os,const MinHeap& p) 
{ 
	for(int i=0;i