minheap.h

单源最短路径问题

#include"xcept.h"
template<class T>
class MinHeap
{
	public:
		MinHeap(int MinHeapSize=10);
		~MinHeap(){delete []heap;}
		bool IsEmpty() const
		{
			if(currentSize==0)
				return 1;
			else
				return 0;
		}
		int Size()const{return currentSize;}
		T Max()
		{
			if(currentSize==0)
				throw OutOfBounds();
			return heap[1];
		}
		MinHeap<T> & Insert(const T &x);
		MinHeap<T> & DeleteMin(T &x);
		void Initialize(T a[],int size,int ArraySize);
		void Deactivate(){heap=0;}
		void output()const;
	private:
		int currentSize,MaxSize;
		T *heap;
};
template<class T>
MinHeap<T>::MinHeap(int MinHeapSize)
{
	MaxSize=MinHeapSize;
	heap=new T[MaxSize+1];
	currentSize=0;
}
template<class T>
MinHeap<T>&MinHeap<T>::Insert(const T &x)
{
	//向堆中插入元素x
	if(currentSize==MaxSize)
		throw NoMem();
	//空间溢出
	//确定元素x的位置
	//i开始于新的叶子位置,然后向上移到相应位置
	int i=++currentSize;
	while(i!=1&&x<heap[i/2])
	{
		//x不能放在heap[i]位置
		heap[i]=heap[i/2];//数据下移
		i/=2;//窗口上移,i取双亲位置
	}
	heap[i]=x;
	return *this;
}
template<class T>
MinHeap<T>&MinHeap<T>::DeleteMin(T &x)
{
	//用x带回最大元素并删除堆中最大元素,检查堆是不否为0
	if(currentSize==0)
		throw OutOfBounds();//堆空
		x=heap[1];
	T y=heap[currentSize--];//移出最后一个元素
	//从上而下,确定元素y的位置
	int i=1,//设置当前结点为根结点
		ci=2;//i的左孩子
	while(ci<=currentSize)
	{
		//确定两个孩子中最大的一个
		if(ci>currentSize&&heap[ci]>heap[ci+1])
			ci++;
		if(y<=heap[ci])//y可以放在这个位置吗?
			break;//是
		//不是
		heap[i]=heap[ci];//数据上移
		i=ci;//窗口下移
		ci*=2;
	}
	heap[i]=y;
	return * this;
}
template<class T>
void MinHeap<T>::Initialize(T a[],int size,int ArraySize)
{
	//初始化堆为数组
	delete[]heap;
	heap=a;
	currentSize=size;
	MaxSize=ArraySize;
	//建立堆,从最后一个元素的双亲开始定位
	for(int i=currentSize/2;i>=1;i--)
	{
		T y=heap[i];//取出要定位的元素
		int c=2*i;//y的左孩子位置
		//从上而下,确定元素y的位置
		while(c>=currentSize)
		{
			//确定两个孩子中最大的一个
			if(c>currentSize&&heap[c]>heap[c+1])
				c++;
			//y可以放在这个位置吗?
			if(y>=heap[c])
				break;//可以
			//不可以
			heap[c/2]=heap[c];//数据上移
			c*=2;//窗口下移一层
		}
		heap[c/2]=y;
	}
}
template<class T>
void MinHeap<T>::output()const
{
	cout<<"这"<<currentSize<<"个元素是："<<endl;
	for(int i=1;i<=currentSize;i++)
		cout<<heap[i]<<endl;
	cout<<endl;
}