template <class T>
class MinHeap  
{
private:
	T* heapArray;
	int CurrentSize;
	int MaxSize;
public:
	MinHeap(const int n);
	virtual ~MinHeap()
	{delete []heapArray;};
	void BuildHeap();
	bool isLeaf(int pos) const;
	int leftchild(int pos) const;
	int rightchild(int pos) const;
	// Return parent position
	int parent(int pos) const;
	// 刪除給定下標的元素
	bool Remove(int pos, T& node);
	void SiftDown(int left);
	//從position向上開始調整，使序列成為堆
	void SiftUp(int position); 
	bool Insert(const T& newNode);
	T& RemoveMin();
};

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

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

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

template<class T>
int MinHeap<T>::leftchild(int pos) const
{
	return 2*pos+1;						//返回左孩子位置
}

template<class T>
int MinHeap<T>::rightchild(int pos) const
{
	return 2*pos+2;						//返回右孩子位置
}

template<class T>
int MinHeap<T>::parent(int pos) const	// 返回父節點位置
{
	return (pos-1)/2;
}

template<class T>
void MinHeap<T>::SiftDown(int left)
{
	//準備
	int i=left;							//標識父結點
	int j=2*i+1;						//標識關鍵值較小的子結點		
	T	temp=heapArray[i];				//保存父結點
	//過篩
	while(j<CurrentSize)
	{
		if((j<CurrentSize-1)&&(heapArray[j]>heapArray[j+1]))
			j++;						//j指向右子結點
		if(temp>heapArray[j])
		{
			heapArray[i]=heapArray[j];
			i=j;
			j=2*j+1;
		}
		else break;
	}
	heapArray[i]=temp;
}

template<class T>
void MinHeap<T>::SiftUp(int position) 
{//從position向上開始調整，使序列成為堆
	int temppos=position;
	T temp=heapArray[temppos];
	while((temppos>0)&&(heapArray[parent(temppos)]>temp))
	{
		heapArray[temppos]=heapArray[parent(temppos)];
		temppos=parent(temppos);
	}
	heapArray[temppos]=temp;
}

template<class T>
bool MinHeap<T>::Insert(const T& newNode)
{//向堆中插入一個結點
	if(CurrentSize==MaxSize)
		return FALSE;
	heapArray[CurrentSize]=newNode;
	SiftUp(CurrentSize);
	CurrentSize++;
}

template<class T>
T& MinHeap<T>::RemoveMin()
{
	if(CurrentSize==0)
	{
		AfxMessageBox("Can't Delete");

	}
	else
	{
		T temp=heapArray[0];					//取堆頂元素
		heapArray[0]=heapArray[CurrentSize-1];	//堆末元素上升至堆頂
		CurrentSize--;
		if(CurrentSize>1)
			SiftDown(0);						//從堆頂開始篩選
		return temp;
	}
}

template<class T>
bool MinHeap<T>::Remove(int pos, T& node)
{// 刪除給定下標的元素
	if((pos<0)||(pos>=CurrentSize))
		return false;
	T temp=heapArray[pos];
	heapArray[pos]=heapArray[--CurrentSize];	//指定元素置于最后
	SiftUp(pos);								//上升篩
	SiftDown(pos);								//向下篩	
	node=temp;
	return true;
}