头文件 _BinHeap.h

#ifndef _BinHeap_H

struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;

PriorityQueue Initialize( int MaxElements );
void Destroy( PriorityQueue H );
void MakeEmpty( PriorityQueue H );
void Insert( ElementType X, PriorityQueue H );
ElementType DeleteMin( PriorityQueue H );
ElementType FindMin( PriorityQueue H );
int IsEmpty( PriorityQueue H );
int IsFull( PriorityQueue H );
void DecreaseKey( ElementType X, int C, PriorityQueue H );
void IncreaseKey( ElementType X, int C, PriorityQueue H );
ElementType Delete( ElementType X, PriorityQueue H );

#endif

/* Place in the implementation */
struct HeapStruct
{
	int Capacity;
	int Size;
	ElementType *Elements;
};

主要例程

PriorityQueue Initialize( int MaxElements )
{
	PriorityQueue H;
	if( MaxElements < MinPQSize )
	{
		printf( "Priority Queue size is too small!!!" );
		exit( 1 );
	}

	H = malloc( sizeof( struct HeapStruct ) );
	if( H == NULL )
	{
		printf( "Out of space !!!" );
		exit( 1 );
	}
	/* Allocate the array plus one extra for sentinel */
	H->Elements = malloc( sizeof( ElementType ) * (MaxElements + 1 ) );
	if( H->Elements == NULL )
	{
		printf( "Out of space !!!" );
		exit( 1 );
	}

	H->Capacity = MaxElements;
	H->Size = 0;
	H->Elements[ 0 ] = MinData;

	return H;
}

void Insert( ElementType X, PriorityQueue H )
{
	int i;

	for( IsFull( H ) )
	{
		printf( "Priority queue is full" );
		exit( 1 );
	}
	for( i = ++H->Size; H->Elements[ i / 2 ] > X; i /= 2 )
		H->Elements[ i ] = H->Elements[ i / 2 ];
	H->Elements[ i ] = X;
}

ElementType DeleteMin( PriorityQueue H )
{
	int i, Child;
	ElementType MinElement, LastElement;

	if( IsEmpty( H ) )
	{
		printf( "Priority queue is empty" );
		return H->Elements[ 0 ];
	}
	MinElement = H->Elements[ 1 ];
	LastElement = H->Elements[ H->Size-- ];

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

		if( LastElement > H->Elements[ Child ] )
			H->Elements[ i ] = H->Elements[ Child ];
		else
			break;
	}

	H->Elements[ i ] = LastElement;

	return MinElement;
}

ElementType FindMin( PriorityQueue H )
{
	if( IsEmpty( H ) )
	{
		printf( "Priority queue is empty!" );
		return;
	}
	return H->Elements[ 1 ];
}

int IsEmpty( PriorityQueue H )
{
	return H->Size == 0;
}

int IsFull( PriorityQueue H )
{
	return H->Capacity == H->Size;
}

void DecreaseKey( int Position, ElementType Change, PriorityQueue H )
{
	ElementType TempCell;
	if( Position <= 0 || Position > H->Size )
	{
		printf( "Wrong Position!" );
		return;
	}
	TempCell = H->Elements[ Position ] - Change;
	while( H->Elements[ Position / 2 ] > TempCell )
	{
		H->Elements[ P ] = H->Elements[ P / 2 ];
		P /= 2;
	}
	H->Elements[ P ] = TempCell;
}

void IncreaseKey( int Position, int Change, PriorityQueue H )
{
	ElementType TempCell;
	if( Position <= 0 || Position > H->Size )
	{
		printf( "Wrong Position!" );
		return;
	}

	TempCell = H->Elements[ Position ] + Change;

	while( P * 2 <= H->Size )
	{
		Child = P * 2;
		if( Child != H->Size && H->Elements[ Child + 1 ] < H->Elements[ Child ] )
			Child++;

		if( TempCell > H->Elements[ Child ] )
			H->Elements[ P ] = H->Elements[ Child ];
		else
			break;

		P = Child;
	}
	H->Elements[ Child ] = TempCell;
}

/* 删除某个元素，将该元素值增加到无穷大，然后删除最后一个元素 */
void Delete( int Position, PriorityQueue H )
{
	IncreaseKey( Position, 9999, H );
	H->Size--;
}