// MaxHeap.h: interface for the MaxHeap class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_MaxHeap_H__6BC12E9A_B926_47C2_8ACF_AA4004A0546F__INCLUDED_)
#define AFX_MaxHeap_H__6BC12E9A_B926_47C2_8ACF_AA4004A0546F__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

template <class T>
class MaxHeap  
{
private:
	T* heapArray;							//存放堆數據的數組
	int CurrentSize;						//當前堆中元素數目
	int MaxSize;							//堆所能容納的最大元素數目
public:
	MaxHeap(T* array,int num,int max);
	virtual ~MaxHeap(){};					//析構函數
	void BuildHeap();
	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);			//刪除給定下標的元素
	void SiftDown(int left);				//篩選法函數，參數left表示開始處理的數組下標
	void SiftUp(int position);			 	//從position向上開始調整，使序列成為堆
	BOOL Insert(const T& newNode);			//向堆中插入新元素newNode
	void MoveMax();							//從堆頂移動最大值到尾部
	T& RemoveMax();							//從堆頂刪除最大值
};

template<class T>
MaxHeap<T>::MaxHeap(T* array,int num,int max)
{
	heapArray=array;
	CurrentSize=num;
	MaxSize=max;
	BuildHeap();
}

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

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

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

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

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

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

template<class T>
BOOL MaxHeap<T>::Insert(const T& newNode)
{//向堆中插入一個結點
	if(CurrentSize==MaxSize)				//堆空間已經滿
		return FALSE;
	heapArray[CurrentSize]=newNode;
	SiftUp(CurrentSize);					//向上調整
	CurrentSize++;
}

template<class T>
T& MaxHeap<T>::RemoveMax()
{
	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>
void MaxHeap<T>::MoveMax()
{
	if(CurrentSize==0)
	{
		//堆為空
		return;
	}
	else
	{
		T temp=heapArray[0];					//取堆頂元素
		heapArray[0]=heapArray[CurrentSize-1];	//堆末元素上升至堆頂
		CurrentSize--;
		if(CurrentSize>1)
			SiftDown(0);						//從堆頂開始篩選
		heapArray[CurrentSize]=temp;
	}
	return;
}

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

#endif // !defined(AFX_MaxHeap_H__6BC12E9A_B926_47C2_8ACF_AA4004A0546F__INCLUDED_)