优先队列（priority_queue)和一般队列(queue)的函数接口一致，不同的是，优先队列每次出列的是整个队列中最小（或者最大）的元素。
本文简要介绍一种基于数组二叉堆实现的优先队列，定义的数据结构和实现的函数接口说明如下：
一、键值对结构体：KeyValue
key_value_new用于创建一个KeyValue结构体；key_value_free用于释放一个KeyValue结构体的内存，
参数freevalue用于释放数据指针_value指向的内存。
二、优先队列结构体：PriorityQueue
int _priority;
};
PriorityQueue *priority_queue_new(int priority);
void priority_queue_free(PriorityQueue *pq, void (*freevalue)(void *));
const KeyValue *priority_queue_top(PriorityQueue *pq);
KeyValue *priority_queue_dequeue(PriorityQueue *pq);
void priority_queue_enqueue(PriorityQueue *pq, KeyValue *kv);
int priority_queue_size(PriorityQueue *pq);
int priority_queue_empty(PriorityQueue *pq);
void priority_queue_print(PriorityQueue *pq);
</div>
1) 其中nodes字段是二叉堆数组，_capacity是nodes指向的KeyValue*指针的个数，_size是nodes中实际存储的元素个数。
_priority可以是PRIORITY_MAX或PRIORITY_MIN，分别表示最大元素优先和最小元素优先。
2) priority_queue_new和priority_queue_free分别用于创建和释放优先队列。
3) priority_queue_top用于取得队列头部元素，
4）priority_queue_dequeue用于取得队列头部元素并将元素出列。
其实现的基本思路，以最大优先队列说明如下：
①将队列首部nodes[0]保存作为返回值
②将队列尾部nodes[_size-1]置于nodes[0]位置，并令_size=_size-1
③令当前父节点parent(nodes[i])等于新的队列首部(i=0)元素，
parent指向元素的儿子节点为left = nodes[2 * i + 1]和rigth = nodes[2 * i + 2]，
比较left和right得到优先级高的儿子节点,设为nodes[j](j = 2 *i + 1或2 *i + 2)，
④如果当前父节点parent的优先级高于nodes[j]，交换nodes[i]和nodes[j]，并更新当前父节点,
即令i=j,并循环 ③；
如果当前父节点的优先级低于nodes[j],处理结束。
5）priority_queue_enqueue用于将KeyValue入列
其实现的基本思路，以最大优先队列说明如下：
①设置nodes[_size] 为新的KeyValue,并令_size++
②令当前儿子节点child(nodes[i])为新的队列尾部节点（i=_size-1)，child的父节点parent为nodes[j],
其中j= (i - 1) / 2
③如果当前儿子节点child的优先级高于parent, 交换nodes[i]和nodes[j]，并更新当前儿子节点
即令i = j,并循环③;
如果当前儿子节点的优先级低于parent,处理结束。
6) priority_queue_size用于取得队列中元素个数，priority_queue_empty用于判断队列是否为空。
7）priority_queue_print用于输出队列中的内容。
文件pq.h给出了数据结构和函数的声明，文件pq.c给出了具体实现，main.c文件用于测试。虽然是使用过程化编程的C语言，可以看到具体的编码中应用了基于对象的思想，我们对数据结构和相关函数做了一定程度的聚集和封装。
// =============KeyValue Struct==================================
typedef struct key_value_struct KeyValue;
struct key_value_struct
{
int _key;
void *_value;
};
KeyValue *key_value_new(int key, void *value);
void key_value_free(KeyValue *kv, void (*freevalue)(void *));
// =============PriorityQueue Struct==============================
#define PRIORITY_MAX 1
#define PRIORITY_MIN 2
typedef struct priority_queue_struct PriorityQueue;
struct priority_queue_struct
{
KeyValue **_nodes;
int _size;
int _capacity;
int _priority;
};
PriorityQueue *priority_queue_new(int priority);
void priority_queue_free(PriorityQueue *pq, void (*freevalue)(void *));
const KeyValue *priority_queue_top(PriorityQueue *pq);
KeyValue *priority_queue_dequeue(PriorityQueue *pq);
void priority_queue_enqueue(PriorityQueue *pq, KeyValue *kv);
int priority_queue_size(PriorityQueue *pq);
int priority_queue_empty(PriorityQueue *pq);
void priority_queue_print(PriorityQueue *pq);
#endif
/*
*File:pq.c
*purpose: definition of priority queue in C
*Author:puresky
*Date:2011/04/27
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "pq.h"
//Private Functions
static void priority_queue_realloc(PriorityQueue *pq);
static void priority_queue_adjust_head(PriorityQueue *pq);
static void priority_queue_adjust_tail(PriorityQueue *pq);
static int priority_queue_compare(PriorityQueue *pq,
int pos1,
int pos2);
static void priority_queue_swap(KeyValue **nodes,
int pos1,
int pos2);
//Functions of KeyValue Struct
KeyValue *key_value_new(int key,
void *value)
{
KeyValue *pkv = (KeyValue *)malloc(sizeof(KeyValue));
pkv->_key = key;
pkv->_value = value;
return pkv;
}
void key_value_free(KeyValue *kv,
void (*freevalue)(void *))
{
if(kv)
{
if(freevalue)
{
freevalue(kv->_value);
}
free(kv);
}
}
//Functions of PriorityQueue Struct
PriorityQueue *priority_queue_new(int priority)
{
PriorityQueue *pq = (PriorityQueue *)malloc(sizeof(PriorityQueue));
pq->_capacity = 11; //default initial value
pq->_size = 0;
pq->_priority = priority;
pq-