优先队列：顾名思义，这个队列中的元素是有优先级的，它和普通的先进先出（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#include #include 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;} 堆的其他操作都很简单。