优先队列的一种实现--堆ADT

二叉堆的两个重要性质：

1、结构性，为完全二叉树，可以用数组方便地表示。2、堆序性：树中每个节点的关键字值大于或等于其父节点的关键字值。

二叉堆的数据结构声明如下：

 1 struct HeapStruct;
 2 typedef struct HeapStruct *PriorityQueue;
 3 
 4 PriorityQueue Initialize(int MaxElements);
 5 void Destroy(PriorityQueue H);
 6 void MakeEmpty(PriorityQueue H);
 7 void Insert(ElementType X, PriorityQueue H);
 8 ElementType FindMin(PriorityQueue H);
 9 ElementType DeleteMin(PriorityQueue H);
10 int isEmpty(PriorityQueue H);
11 int isFull(PriorityQueue H);
12 
13 struct HeapStruct{
14     int Capacity;
15     int size;
16     ElementType *Elements;
17 };

初始化函数代码如下：

 1 PriorityQueue Initialize(int MaxElements){
 2     PriorityQueue H;
 3 
 4     H = malloc(sizeof(HeapStruct));
 5     H->Elements = malloc((MaxElements+1)*sizeof(ElementType));
 6 
 7     H->Capacity = MaxElements;
 8     H->size = 0;
 9     return H;
10 }

Insert函数实现代码如下：

 1 void Insert(ElementType X, PriorityQueue H){
 2     int i;
 3 
 4     if(isFull(H)){
 5         printf("Heap is full
");
 6         return;
 7     }
 8     for(i=++H->size; i>1 && H->Elements[i/2] > X; i /=2)
 9             H->Elements[i] = H->Elements[i/2];
10     
11     H->Elements[i] = X;
12 }

DeleteMin函数实现代码如下：

 1 ElementType DeleteMin(PriorityQueue H){
 2     int i, Child;
 3     ElementType MinElement, LastElement;
 4 
 5     if(isEmpty(H)){
 6         printf("Priority queue is empty
");
 7         return MinData; //无意义的堆中比最小值还小的值
 8     }
 9 
10     MinElement = H->Elements[1];
11     LastElement = H->Elements[H->size--];
12 
13     for(i=1; i*2<=H->size; i=Child){
14         Child = i*2;
15         if(Child != H->Size && H->Elements[Child + 1] < H->Elements[Child])
16             Child++;
17         if(LastElement > H->Elements[Child])
18             H->Elements[i] = H->Elements[Child];
19         else
20             break;
21     }
22     H->Elements[i] = LastElement;
23     return MinElement;
24 }