数据结构学习之二叉堆

#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);

#endif
//一个堆数据结构将由一个数组，一个代表最大值的整数以及当前的堆大小组成
struct HeapStruct
{
int Capacity;
int Size;
ElementType *Elements;
}
//堆序性：在一个堆中，对于每一个节点X，X的父亲节点中的关键字小于或等于X中的关键字（根节点除外）

//优先队列的声明

PriorityQueue Initialize(int MaxElements)
{
PriorityQueue H;
if(MaxElements<MinPQSize)
Error("PriorityQueue size is too small");
H=malloc(sizeof(struct HeapStruct));
if(H==NULL)
FatalError("out of space");
H->Elements=malloc((MaxElements+1)*sizeof(ElementType));
if(H->Elements==NULL)
FatalError("out if space");
H->Capacity=MaxElements;
H->Size=0;
H->Elements[0]=MinData;
return H;
}
//插入一个二叉堆
void Insert(ElementType X.PriorityQueue H)
{
int i;
if(IsFull(H))
{
Error("PriorityQueue is full");
return ;
}
for(i=++H->Size;H->Elements[i/2]>X;i/=2)
/*对于数组中的任一位置i上的元素，其左儿子在位置2i上
右儿子在左儿子后的单元(2i+1),他的父亲在(1/2)
*/
H->Elements[i]=H->Elements[1/2];
H->Elements[i]=X;
}
//在二叉堆中执行DeleteMin
ElementType DeleteMin(PriorityQueue H)
{
int i,Child;
ElementType MaxElement,LastElement;
if(IsEmpty(H)
{
Error("PriorityQueue 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;
}
int IsEmpty( PriorityQueue H )
{
return H->Size == 0;
}

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

void Destroy( PriorityQueue H )
{
free( H->Elements );
free( H );
}
ElementType FindMin( PriorityQueue H )
{
if( !IsEmpty( H ) )
return H->Elements[ 1 ];
Error( "Priority Queue is Empty" );
return H->Elements[ 0 ];
}