minheap.h

霍夫曼树的代码..实现了用霍夫曼编码的功能,经测试能成功输出

#include <iostream>
using namespace std;

template <class T>
class MinHeap
{
private:
	T *heapArray;
	int CurrentSize;
	int MaxSize;
	void swap(int x,int y);
	void BuildHeap();
public:
	MinHeap(const int n)
	virtual ~(MinHeap{delete [] heapArray;}
	bool isEmpty();
	bool isLeaf(int pos); const;
	int LeftChild(int pos) const;
	int RightChild(int pos) const;
	int Parent(int pos) const;
	bool Remove(int pos, int & node);
	bool Insert(const int & newNode);
	T & RemoveMin();
	void SiftUp(int pos);
	void SiftDown(int pos);
};

template <class T>
MinHeap::MinHeap(const int n)
{
	if(n<=0)
		return;
	CurrentSize=0;
	MaxSize=n;
	heapArray=new T[n];
	BuildHeap();
}

template <class T>
bool MinHeap::isLeaf(int pos) const;
{
	if(pos>=CurrentSize/2)&&(pos<CurrentSize) return true;
	else return false;
}

template <class T>
void MinHeap::swap(int pos_x, int pos_y)
{
	int temp;
	temp=heapArray[pos_x];
	heapArray[pos_x]=heapArray[pos_y];
	heapArray[pos_y]=temp;
}

template <class T>
void MinHeap::BuildHeap
{
	for(int i=CurrentSize/2-1;i>=0;i--)
		SiftDown(i);
}

template <class T>
int MinHeap::LeftChild(int pos) const
{
	return 2*pos+1;
}

template <class T>
int MinHeap::RightChild(int pos) const
{
	return 2*pos+2;
}

template <class T>
bool MinHeap::Insert(const T & newNode)
{
	if(CurrentSize==Maxsize)
		return false;
	heapArray[CurrentSize]=newNode;
	SiftUp(CurrentSize);
	CurrentSize++;
	return true;
}

template <class T>
T & MinHeap::RemoveMin()
{
	if(CurrentSize==0)
	{
		cout<<"cannot delete"<<endl;
		return 0;
	}
	swap(0,--Current);
	if(CurrentSize>1)
		SiftDown(0);
	return heapArray[CurrentSize];
}

template <class T>
void MinHeap::SiftUp(int pos)
{
	int temppos=pos;
	T temp=heapArray[temppos];
	while(temppos>0&&heapArray[Parent(temppos)]>temp)
	{
		heapArray[temppos]=heapArray[Parent(temppos)];
		temppos=Parent(temppos);
	}
	heap[Array[temppos]=temp;
}

template <class T>
void MinHeap::SiftDown(int pos)
{
	int i=pos;
	int j=LeftChild(i);
	T temp=heapArray[pos];
	while(j<CurrentSize)
	{
		if((j<CurrentSize-1)&&(heapArray[j]>heapArray[j+1]))
			j++;
		if(temp>heapArray[j])
		{
			heapArray[i]=heapArray[j];
			i=j;
			j=LeftChild(j);
		}
		else break;
	}
	heapArray[i]=temp;
}