优先队列（堆实现）

优先队列由二叉堆实现是很普遍的事情。

下面我把二叉堆也称作为堆。

堆是一棵被完全填满的二叉树，一棵高为h的二叉树2^h到2^h+1-1个节点。这意味着完全二叉树的高时log N。

因为完全二叉树很有规律，所有它可以用一个数组来表示，而不需要指针

对于这棵树，我们可以这样表示。

对于数组中任意一个位置 i 上的元素，其左儿子在位置 2 i 上，右儿子在左儿子后的单元（2 i + 1 ）,它的父亲则在位置（ i / 2 ）上。

 1 #ifndef _BinHeap_H
 2 
 3 struct HeapStruct;
 4 
 5 typedef int ElementType
 6 
 7 typedef struct HeapStruct *PriorityQueue;
 8 
 9 PriorityQueue Initialize (int MaxElenments);
10 
11 void Destroy(PriorityQueue H);
12 
13 void MakeEmpty(PriorityQueue H);
14 
15 void Insert(ElementType X,PriorityQueue H);
16 
17 ElementType DeleteMin(PriorityQueue H);
18 
19 ElementType Find(PriorityQueue H);
20 
21 int IsEmpty(PriorityQueue H);
22 
23 int Is Full (PriorityQueue H);
24 
25 
26 #endif // _BinHeap_H
27 
28 struct HeapStruct{
29     int Capacity;
30     int Size;
31     ElementType *Elements;
32 };

 1 //对堆进行初始化
 2 PriorityQueue Initialize(int MaxElements)
 3 {
 4     PriorityQueue H;
 5     
 6     if(MaxElements < MinPQsize)
 7         Error("Priority queue size is too small");
 8     
 9     H = malloc(sizeof( struct HeapStruct));   //H等于HeapStruct的内存大小，malloc是向系统申请一个内存空间。
10     if(H == NULL)
11         FatelError ("Out of space!!!");
12     H->Elements = malloc((MaxElements+1)*sizeof(ElementType));  //申请一个内存空间，之后就可以像数组一样对Elements进行操作。
13     
14 
15     if(H->Elements == NULL)
16         FatalError("Out of space!!!");   //H没有子节点了。
17     
18     H->Capacity = MaxElements;
19     H->Size = 0;
20     H->Elements[0] = MinDate
21     
22     return H;
23 }

 1 // 插入元素
 2 
 3 void Insert(ElementType X, PriorityQueue H )
 4 {
 5     int i;
 6     if(IsFull(H))
 7     {
 8         Error("Priority queue is full");
 9         return ;
10     }
11     for(int i = ++H->Size;H->Elements[i/2]>X;i /= 2)   //采用冒泡，一个冒上去。
12         H->Elements[i] = H->Elements[i/2];    //如果它比它的父亲节点小的话，那么冒泡上去。
13     H->Elements[i] = X;
14 }

 1 //删除最小值
 2 
 3 ElementType DeleteMin( PriorityQueue H )
 4 {
 5     int i,Child;
 6     ElemenType MinElement , LastElement;
 7     
 8     if(IsEmpty( H ))
 9     {
10         Error("Priority queue is empty");
11         return H->Elements[ 0 ];
12     }
13     MinElement = H->Elements[ 1 ];
14     LastElement = H->Elements[ H->Size-- ];
15     
16     for( i = 1;i * 2 <= H->Size; i = Child )     //将每一个子节点的最小值上升到原来的父亲节点。
17     {
18         Child = i * 2;
19         if( Child != H->Size && H->Elements[ Child+1 ]
20                              <  H->Elements[ Child ] )
21             Child++;
22         
23         if( LastElement > H->Elements[ Child ])
24             H->Elements[i] = H->Elements[ Child ];
25         else 
26             break;
27     }
28     H->Elements[ i ] = LastElement;
29     return MinElement; 
30     
31 }

自己写的便于套用的一个堆

 1 int arr[]
 2 
 3 void inset(int x,int y)
 4 {
 5     int i;
 6     for(i = y; arr[ i / 2 ] > x;i /= 2)
 7         arr[ i ] = arr[ i / 2 ];
 8     arr[ i ] = x;
 9 }
10 
11 int deleteMin(int x)
12 {
13     int i, child;
14     int Min,last;
15     Min = arr[1],last = arr[ x ];
16     for(i = 1; i * 2 <= x; i = child )
17     {
18         child = i * 2;
19         if( child != x && arr[ child+1 ]
20                         < arr[ child ] )
21             child++;
22         if(last > arr[ child ])
23             arr[ i ] = arr[ child ];
24         else
25             break;
26     }
27 
28     arr[ i ] = last;
29     return Min;
30 }