minheap.cpp

这些程序是本人学习数据结构时编的

// MinHeap.cpp: implementation of the MinHeap class.
//
//////////////////////////////////////////////////////////////////////

#include "MinHeap.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

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(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>
const MinHeap<Type>& MinHeap<Type>::operator =(const MinHeap &R)
{
	int i =0;
	while(i<= R.CurrentSize)
	{
		heap[i] = R.heap[i];
		i++;
	}
	CurrentSize = R.CurrentSize;
	return this;
}

template<class Type>
int MinHeap<Type>::Insert(const Type &x)
{
	if (CurrentSize == MaxHeapSize )
	{
		cerr <<"Heap Full"<<endl;
		return 0;
	}
	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;
}

template<class Type>
void MinHeap<Type>::MakeEmpty()
{
	CurrentSize = 0;
}

template<class Type>
int MinHeap<Type>::IsFull() const
{
	return CurrentSize ==0;
}

template<class Type>
int MinHeap<Type>::IsEmpty() const
{
	return CurrentSize == MaxHeapSize;
}

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;
}