堆结构.cpp

算法分析中

/*
堆结构：
堆就是一棵完全二叉树
数组来存储各个结点
数组中任一位置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;
		};
};