minheap.cpp

插入和删除最小元素操作

// MinHeap.cpp: implementation of the MinHeap class.
//
//////////////////////////////////////////////////////////////////////

#include "MinHeap.h"
#include <cmath>

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

MinHeap::MinHeap( int sz )
{
	MaxSize = sz;
	n = 0;
	heap = new Element [ MaxSize + 1 ];
}

void MinHeap::Insert( const Element& x )
{
	if( n == MaxSize ) return;
	n++;
	for( int i = n; i > 1; )
	{
		if(x.key >= heap[i/2].key) break;

		heap[i] = heap[i/2];
		i/=2;
	}
	heap[i] = x;
}

Element* MinHeap::Delete( Element& del )
{
	Element x;

	if(!n)
	{
		return 0;
	}
		x = heap[1]; Element k = heap[n]; heap[n].key = 0; n--;

		for( int i = 1, j = 2; j <= n; )
		{
			if( j < n )
				if( heap[j].key > heap[j+1].key )
					j++;
				if( k.key <= heap[j].key )
					break;
				heap[i] = heap[j];
				i = j;
				j *= 2;
		}
		heap[i] = k;
		return &x;
}