minheap.h

最小堆头文件(C++)

template <class Type>
class MinHeap{
	public:
		MinHeap(int maxSize);
		MinHeap(Type a [], int n);
		~MinHeap() {delete [] heapArr;}
		int Insert(const Type & d);
		Type DeleteTop();
		Type GetTop() const
			{return heapArr[0];}
		int IsEmpty() const
			{return heapCurrentSize == 0;}
		int IsFull() const
			{return heapCurrentSize == heapMaxSize;}
		int SizeofHeap() const
			{return heapCurrentSize;}
		void SetEmpty()
			{heapCurrentSize = 0;}
	private:
		Type * heapArr;
		int heapCurrentSize;
		int heapMaxSize;
		void FilterDown(const int start);
		void FilterUp(int p);
};

template <class Type>
MinHeap<Type>::MinHeap(int maxSize){
	if (maxSize <= 0){
		cerr << "The size of heap cannot be less than 1" << endl;
		exit(1);
	}
	heapMaxSize = maxSize;
	heapArr = new Type [heapMaxSize];
	heapCurrentSize = 0;
}

template <class Type>
MinHeap<Type>::MinHeap(Type a[], int n){
	if (n <= 0){
		cerr << "The size of heap cannot be less than 1" << endl;
		exit(1);
	}
	heapMaxSize = n;
	heapArr = new Type [heapMaxSize];
	heapArr = a;
	heapCurrentSize = n;
	int i = (heapCurrentSize - 2) / 2;
	while (i >= 0){
		FilterDown(i);
		i--;
	}
}

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

template <class Type>
int MinHeap<Type>::Insert(const Type & d){
	if (IsFull())
		{cout << "The heap is full" << endl; return 0;}
	heapArr[heapCurrentSize] = d;
	FilterUp(heapCurrentSize);
	heapCurrentSize++;
	return 1;
}

template <class Type>
void MinHeap<Type>::FilterUp(int p){
	int j = p, i;
	Type temp = heapArr[j];
	i = (j - 1) / 2;
	while (j > 0){
		if (heapArr[i].key <= temp.key)	break;
		else {
			heapArr[j] = heapArr[i];
			j = i; i = (j - 1) / 2;
		}
	}
	heapArr[j] = temp;
}

template <class Type>
Type MinHeap<Type>::DeleteTop(){
	if (IsEmpty()){
		cout << "The heap is empty" << endl;
		return NULL;
	}
	Type temp = heapArr[0];
	heapArr[0] = heapArr[heapCurrentSize - 1];
	heapCurrentSize--;
	FilterDown(0);
	return temp;
}