/*
堆結構：
堆就是一棵完全二叉樹
數組來存儲各個結點
數組中任一位置i上的元素，其左兒子在位置2i上，右兒子在2*i+1上，當然了存儲下標從1開始

堆序性質
在一個堆中，對于每一個結點x，x的父親中的關鍵字小于x中的關鍵字，根結點除外
*/

/*
掌握如何實現優先隊列，利用二叉堆，孩子結點都大于父親結點
*/

template<class Type>
class MaxHeap
{
	public:
		Type *H;
		int Capacity;
		int Size;
	public:
		MaxHeap(int n)
		{
			H = NULL;
			//H = (Type*)malloc( sizeof( Type ) * ( n + 1 ) );
			H = new Type[n+1];
			Capacity = n;
			Size = 0;
		};
		MaxHeap( MaxHeap& a )
		{
			//要排除自賦值的情況
			if ( this.H != a.H )
			{
				this.H = a.H;
				this.Size = a.Size;
				this.Capacity = a.Capacity;
				for( int i = 0; i < Size; ++i )
				{
					this.H[i] = a.H[size];
				}
			}
		};

		/*
		基本的堆插入操作
		為了將node插入到堆中
		首先在下一個空閑位置++Size處，創建一個空穴，否則該堆將不是完全樹
		如果x可以放在該穴中而不破壞堆的序，那么插入完成
		否則我們把空穴的父親結點上的元素移動到該穴中，這樣空穴就朝著根的方向上行一步
		繼續該過程直到x能被放入空穴為止
		*/
		void Insert( Type& node )
		{
			//插入元素的時候按照從大到順序
			for( int i = ++Size; H[ i / 2 ] < node && i != 0; i /= 2 )
			{
				H[i] = H[ i / 2 ];
			}
			//一定要注意從下標一開始的時候，添加如何進行比較才行
			H[i] = node;
			H[1].print();
			
			for( int k = 1; k <= Size; ++k )
			{
				H[k].print();
			}
			
		};

		/*
		當刪除一個最小元時
		在根結點處產生一個空穴。
		由于現在堆少了一個元素，因此堆中最后一個元素必須移動到該堆的某個地方
		如果x可以放到空穴中，那么DeleteMin完成
		否則應該將兩個兒子中較小者移入空穴
		這樣空穴就向下推了一層。重復該步驟直到x可以被放入空穴中
		*/
		void DeleteMin( Type& node )
		{
			int i,Child;
			Type MinElement,LastElement;
			node = H[1];
			LastElement = H[Size--];

			for( i = 1; i * 2 <= Size; i = Child )
			{
				Child = i * 2;
				if ( ( Child != Size && H[ Child + 1 ] > H[ Child ] ) )
				{
					Child++;
				}

				if ( LastElement < H[ Child ] )
				//找到孩子結點中最大的一個覆蓋孩子結點
				{
					H[ i ] = H[ Child ];      
				}
				else
				{
					break;
				}
			}
			//same to H[ Child ] = LastElement
			H[ i ] = LastElement;
		};
};