/****************  算法5.12 堆的類定義和篩選法  **********************/
/****************           MinHeap.h           **********************/

#define FALSE 0
#define TRUE 1

template <class T>
class MinHeap  { 							//最小堆類定義
private:
	T* heapArray;							//存放堆數據的數組
	int CurrentSize;						//當前堆中元素數目
	int MaxSize;							//堆所能容納的最大元素數目
	void swap(int pos_x, int pos_y);		//交換位置x和y的元素
	void BuildHeap();						//建堆
public:
	MinHeap(const int n);				 //構造函數,n表示初始化堆的最大元素數目
	virtual ~MinHeap(){delete []heapArray;}; 	//析構函數
    bool isLeaf(int pos) const;		 	    //如果是葉結點，返回TRUE
	int leftchild(int pos) const;		   	//返回左孩子位置
	int rightchild(int pos) const;			//返回右孩子位置
	int parent(int pos) const;				//返回父結點位置
	bool Remove(int pos, T& node);			//刪除給定下標的元素
	bool Insert(const T& newNode);			//向堆中插入新元素newNode
	T& RemoveMin();				        	//從堆頂刪除最小值
	void SiftUp(int position);			 //從position向上開始調整，使序列成為堆
	void SiftDown(int left);             //篩選法函數，參數left表示開始處理的數組下標
};
template<class T>
MinHeap<T>::MinHeap(const int n)  {
	if(n <= 0)
		return;
	CurrentSize = 0;													
	MaxSize = n;							//初始化堆容量為n
	heapArray = new T[MaxSize];		    //創建堆空間
	//此處進行堆元素的賦值工作
	BuildHeap();
}
template<class T>
bool MinHeap<T>::isLeaf(int pos) const  {
	return (pos >= CurrentSize/2) && (pos < CurrentSize);
}

template<class T>
void MinHeap<T>::BuildHeap()  {
	for (int i = CurrentSize/2-1; i >= 0; i--) 	//反復調用篩選函數
		SiftDown(i);
}

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>
bool MinHeap<T>::Insert(const T& newNode)  {  //向堆中插入新元素newNode
	if(CurrentSize == MaxSize)				   //堆空間已經滿
		return FALSE;
	heapArray[CurrentSize] = newNode;
	SiftUp(CurrentSize);					   //向上調整
	CurrentSize++;
	return TRUE;
}


template<class T>
void MinHeap<T>::swap(int pos_x, int pos_y)     //交換位置x和y的元素
{
 T temp = heapArray[pos_x];
 heapArray[pos_x] = heapArray[pos_y];
 heapArray[pos_y] = temp;
}

template<class T>
T& MinHeap<T>::RemoveMin()	 {				//從堆頂刪除最小值
	if (CurrentSize == 0)  {
		cout<< "Can't Delete" <<endl;
//		exit(0);
	}
	else  {
		swap(0,--CurrentSize);					//交換堆頂和最后一個元素
		if(CurrentSize>1)
			SiftDown(0);						//從堆頂開始篩選
		return heapArray[CurrentSize];
	}
}

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

template <class T>
void MinHeap<T>::SiftDown(int left)  {
	int i = left;						//標識父結點
	int j = leftchild (i);					//標識關鍵值較小的子結點
	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 = leftchild(j);				//向下繼續
		}
		else break;
	}
	heapArray[i] = temp;
}