优先队列（堆）
优先队列：顾名思义，这个队列中的元素是有优先级的，它和普通的先进先出（FIFO）不一样。我们在很多场合可能都需要用到这种特殊的队列（例如，操作系统的进程调度）。
可以看出来，优先队列（priority queue）的核心操作有两个，分别是插入和删除。插入是显而易见的，删除就是找出这个队列中优先级最高的那个元素（可以是最大的，也可是最小的）。
一些简单的想法：我们可以采用一个简单的链表来实现，表头始终存放优先级最高的元素，这样删除操作的时间复杂度就是O(1)，那么相应的插入操作就是O(n)。反过来，插入在表头进行，删除是找出优先级最高元素，这样插入就是O(1),删除就是O(n)。这两种想法都不能得到更好的时间复杂度了。另外，使用BST也可以实现这种操作，但是这通常会使的树变成一颗斜树。导致树的深度很深，也不怎么好用。
二叉堆：完全二叉树经常被用来实现优先队列，因此以至于堆（heap）不加修饰的出现的时候，都是指优先队列这种数据结构。完全二叉树的高度是O(log n)。它非常平衡。这点很重要。另外还有一点就是完全二叉树表现的很有规律。当使用一个数组来保存完全二叉树的时候，从下标为1的地方开始按照层序遍历的方式存储完全二叉树，那么下标为i的节点，它的左儿子在下标为2i的地方保存着，右儿子在下标为2i+1的地方保存着。唯一的缺点是最大的堆的大小需要事先有一个良好的估计。下图是一棵完全二叉树在数组中存储的关系。
我们想快速找出优先级最高的元素，那么优先级最高的放在根上。如果考虑任意的子树也是堆，那么任意节点的优先级都应该高于它的所有后裔。这就是堆序性。在这里我们的堆删除最小元素。因此根节点将比它所有的后裔都小，任意节点也应该小于它所有的后裔。下面给出堆的ADT。
#ifndef HEAP
#define HEAP
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
struct HeapNode
{
int *Heap;
int size; //当前已用容量
int capacity; //总容量
};
typedef struct HeapNode *priorityqueue;
priorityqueue InitHeap(int max); //初始化堆，需要给出堆的最大容量
void DestoryHeap(priorityqueue H); //free掉堆
void Insert(priorityqueue H,int x); //核心操作，插入
int FindMin(priorityqueue H); //这是个附加操作，很容易实现
int DeleteMin(priorityqueue H); //核心操作，删除最小元
int IsFull(priorityqueue H); //数组实现的弊端，必须判断满不满
int IsEmpty(priorityqueue H); //是否空
#endif // !HEAP首先，给出堆的初始化代码，注意，这里是用数组实现的堆。
priorityqueue InitHeap(int max)
{
priorityqueue H = NULL;
H = (priorityqueue)malloc(sizeof(struct HeapNode));
if (NULL == H)
{
printf("创建堆失败！");
exit(0);
}
else
{
H->Heap = (int *)malloc(sizeof(int)*(max + 1)); //因为从下标为1开始放
if (NULL == H->Heap)
{
printf("创建堆失败！");
exit(0);
}
else
{
H->Heap[0] = INT_MIN; //限位器作用
H->capacity = max;
H->size = 0; //初始化没有元素
}
}
return H;
}插入操作：堆的两种基本操作，删除和插入的实现都是简单的，只需要始终保持堆序性即可。首先，插入是在下一个空闲位置创建一个空穴（保证它是完全二叉树）。如果X放在这个空穴处不影响堆序性，那么插入完成。否则将空穴父节点上的元素移动到空穴。一直这样下去，空穴就一直向树根方向移动。直到X能放入该空穴，而不影响堆序性为止。
void Insert(priorityqueue H, int x)
{
if (IsFull(H))
{
printf("堆已满，无法插入！");
//另一种处理方式是realloc()
}
else
{
//++H->size，创建空穴，判断是否影响堆序性。
int i;
for (i = ++H->size; H->Heap[i / 2] > x; i /= 2)
{
H->Heap[i] = H->Heap[i / 2]; //若影响，将父节点的值复制到空穴。
}
H->Heap[i] = x; //若不影响堆序性，则将元素放入空穴。
}
}需要说明的是，在H->Heap[0]中，放入了一个极小的元素，保证x不会比他更小。那么我们就省去了如果新插入的元素是最小值的时候，当i == 1时就要跳出循环的判断了。这就是限位器的作用。这种想法类似于链表添加一个头结点。省去了这个判断，因此程序也能更快点。这种插入在最坏情形下需要O(log n),在平均情形下则要好得多。
删除操作：DeleteMin类似于插入操作，当删除最小元素的时候，那么根将为空。我们需要一个新根。这个新根可以取左右子儿子中小的那一个，这样空穴就被向下退了一层，接着继续比较空穴的左右儿子，选其中小的那个放入空穴，将空穴继续下推，直到将堆中最后一个元素放入空穴为止。
int DeleteMin(priorityqueue H)
{
int i, child;
int min, last_element;
if (IsEmpty(H))
{
printf("堆为空，无法执行删除操作！");
return H->Heap[0]; //返回这个极限值
}
min = H->Heap[1]; //保存最小值
last_element = H->Heap[H->size];
//下滤
for (i = 1; 2 * i <= H->size ; i = child) //i每次更新为下一个空穴的位置
{
child = 2 * i; //左儿子的位置
if (child != H->size && H->Heap[child] > H->Heap[child + 1])
{ //这里需要保证child有另外一个兄弟，所以判断child != H->size
child++; //找出更小的孩子节点
}
if (last_element > H->Heap[child]) //若最后一个元素比这个最小元素还大，那么接着下滤
{
H->Heap[i] = H->Heap[child];
}
else //最后一个不比这个小元素大，那么将其放入空穴，删除完毕。
{
H->Heap[i] = last_element;
break;
}
}
H->size--; //堆中元素数目减1
return min;
}删除的时间复杂度是O（log n）。求最小元的堆在求最大元的时候没有任何帮助，唯一知道的信息是最大元在叶子节点上。但是如果一棵树很大的话，这个信息也没有任何帮助，因为，此时近乎一般的元素在树叶上。所以想知道最大值很困难。
我们可以通过插入操作来构建一个堆，但是这样的时间复杂度高达O（n logn）.因此一般的构建堆的方法是将N个元素直接放入数组中，形成一个完全二叉树。然后把这个不满足堆序性的完全二叉树改造成堆。代码实现如下。
priorityqueue BuildHeap(priorityqueue H)
{
int temp, i = 1;
int start = 1;
while (EOF != scanf("%d",&temp))
{
H->Heap[i++] = temp; //无序数组
}
H->size = i - 1; //堆中元素个数
int parent, child;
int x;
for ( i = H->size / 2; i > 0; i--) //从最后一个元素的父节点开始构建堆
{
//考虑到最后一个元素可能没有兄弟，也可能有兄弟。
x = H->Heap[i];
for (parent = i; parent * 2 <= H->size; parent = child)
{
child = parent * 2; //左儿子一定存在
if ((child != H->size) && (H->Heap[child] > H->Heap[child + 1]))
{
child++; //找到其中最小的那个儿子
}
if (x <= H->Heap[child]) //满足堆序性
{
break; //找到合适位置
}
else //下滤
{
H->Heap[parent] = H->Heap[child];
}
}
H->Heap[parent] = x;
}
return H;
}堆的其他操作都很简单。