minheap.h

算法设计的分支限界法中的单源最短路径问题的实现

#ifndef MinHeap_
#define MinHeap_
#include "xcept.h"
template <class T> class MinHeap
{
public:
	MinHeap(int MinHeapSize=10);
	~MinHeap()
	{
		delete []heap;
	}
	int Size() const
	{
		return currentsize;
	}
	T Min()
	{
		if(currentsize==0)
			throw OutOfBounds();
		return heap[1];
	}
	MinHeap<T> & DeleteMin(T &x);
	int IsEmpty()
	{
		if(currentsize==0)
			return 1;
		else
			return 0;
	}
	void Initialize(T a[],int size,int Arraysize);
	void Deactivate()
	{
		heap=0;
	}
	MinHeap<T> & Insert(const T &x);
	void Output() const;
private:
	int currentsize,Minsize;
	T *heap;
};

template <class T> MinHeap<T>::MinHeap(int MinHeapSize)
{
	Minsize=MinHeapSize;
	heap=new T[Minsize+1];
    currentsize=0;
}

template <class T> MinHeap<T> & MinHeap<T>::Insert(const T &x)
{
	if(currentsize==Minsize)
		throw NoMem();
	int i=++currentsize;
	while(i!=1&&x<heap[i/2])
	{
		heap[i]=heap[i/2];
		i/=2;
	}
	heap[i]=x;
	return *this;	
}

template <class T> MinHeap<T> & MinHeap<T>::DeleteMin(T &x)
{
	if(currentsize==0)
		throw OutOfBounds();
	x=heap[1];
	T y=heap[currentsize--];
	int i=1,ci=2;
	while (ci<=currentsize)
	{
		if(ci>currentsize&&heap[ci]>heap[ci+1])
			ci++;
		if(y<=heap[ci])
			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;
	MinSize=Arraysize;
	for(int i=currentsize/2;i>=1;i--)
	{
		T y=heap[i];
		int c=2*i;
		while(c<=currentsize)
		{
			if(c<currentsize&&heap[c]>heap[c+1])
				c++;
			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]<<ends;
	cout<<endl;
}

#endif