之前一直对优先队列和堆之间的关系有一点点迷惑，昨天整理了堆，堆化以及堆排序的一些内容，今天主要是对于优先队列ADT的一些内容做一些小结，并且清楚优先队列和堆之间的一种关系。
在这浏览这篇博客之前，再温习一遍前文所提到的堆和堆排序
然后我们进入今天的正题。
优先队列
优先队列（Priority Queue)其实就是一种特殊的队列，是一种特殊的数据结构。它的工作就是找出，返回和删除优先队列里的最小(最大）的元素。
insert()函数的实现类似于之前提到的enqueue()，而Delete()函数的实现更像Dequeue()。
优先队列和堆的区别
上篇博客提到的二叉堆只是优先队列的一种实现方式,那如果说优先队列还有哪些实现方式，太多了，二项堆,配对堆,左偏树,斐波那契堆,平衡树，线段树，甚至是二进制分组的vector来实现一个优先队列等等。
比如二项堆和斐波那契堆在之后的博客也会讲述到。
所以说在这儿也就比较清楚了堆和优先队列之间的一种关系。 而二叉堆的堆化以及实现在上一篇的过程已经讲述，就insert()函数来说，插入到树里的元素的位置必须是在整棵树的最后。
如下图红色部分的元素就是新插入到树中的元素。
就Delete(）函数来说，则是对于一棵树的最大堆（最小堆）删除它堆顶的位置。最小堆和最大堆的概念前文已经讲述过，这儿就不再叙述。
堆化的过程前面也已经提到过，这儿则直接上代码。
代码部分
####声明和初始化
typedef int ElementType;
struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;
#define MinPQSize (10)
#define MinData (-32767)//C语言中的整型取值范围是-32768~32767
struct HeapStruct
{
int Capacity;//能容纳的最大个数
int Size; //堆中当前元素个数
ElementType *Elements; //Elements是数组名
};
PriorityQueue Initialize( int MaxElements )
{
PriorityQueue H;
if( MaxElements < MinPQSize )
Error( "Priority queue size is too small" );
H = malloc( sizeof( struct HeapStruct ) );
if( H ==NULL)
FatalError( "Out of space!!!" );
/* Allocate the array plus one extra for sentinel */
H->Elements = malloc( ( MaxElements + 1 )* sizeof( ElementType ) );
if( H->Elements == NULL )
FatalError( "Out of space!!!" );
H->Capacity = MaxElements;
H->Size = 0;
H->Elements[ 0 ] = MinData;
return H;//返回值不要忘了。
}
####insert()
void Insert( ElementType X, PriorityQueue H )
{
int i;
if( IsFull( H ) )
{
Error( "Priority queue is full" );
return;
}
for( i = ++H->Size; H->Elements[ i / 2 ] > X; i /= 2 )
//当i=H->size+1时，判断是否上面的比你这个大，如果大，就交换，一直到头为止
H->Elements[ i ] = H->Elements[ i / 2 ];
H->Elements[ i ] = X;
//这儿用一个swap函数也是可以的
}
####DeleteMin()
ElementType DeleteMin( PriorityQueue H )
{
int i, Child;
ElementType MinElement, LastElement;
if( IsEmpty( H ) )
{
Error( "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 )
{//当parent为1时，做一个不断向下perc down的过程，把孩子赋给parent
/* Find smaller child */
Child = i * 2;
if( Child != H->Size && H->Elements[ Child + 1 ]
< H->Elements[ Child ] )
Child++;//child指向左右孩子的最小值（如果是最大堆这为大于号）
/* Percolate one level */
if( LastElement > H->Elements[ Child ] )
H->Elements[ i ] = H->Elements[ Child ];
else
break;
}
H->Elements[ i ] = LastElement;
return MinElement;
}
####percdown()
void PercDown(PriorityQueue H, int p) { //以p为根结点做percdown,调整为最小堆
int Parent, Child;//i和parent一样
ElementType X;//和上面的last_node一样
X = H->Data[p];
for(parent=p; Parent*2<=H->Size; Parent=Child) {
Child = Parent*2;
if((Child != H->Size)&&(H->Data[Child]>H->Data[Child+1])) { //如果是最小堆是child<child+1
Child++;
}
if(X >= H->Elements[Child]) break;
else {
H->Elements[Parent] = H->Elements[Child];
}
}
H->Elements[Parent] = X; }
####buildheap()
void BuildHeap(PriortyQueue H) {
int i;
for(i=H->Size/2; i>0; i--) {
PercDown(H, i);
}
}
####查找
ElementType FindMin( PriorityQueue H )
{
if( !IsEmpty( H ) )
return H->Elements[ 1 ];
Error( "Priority Queue is Empty" );
return H->Elements[ 0 ];
}
####判断是否为空
int IsEmpty( PriorityQueue H )
{
return H->Size == 0;
} ####判断是否为满
int IsFull( PriorityQueue H )
{
return H->Size == H->Capacity;
}
####Destroy()
void Destroy( PriorityQueue H )
{
free( H->Elements );
free( H );
}
for( i = N / 2; i > 0; i-- )
PercolateDown( i );
