---

首先明确优先级队列的两个表象：

1. 插入元素
2. 删除最小元素

能够实现上述两个操作的数据结构-----优先级队列。

我们可以使用数组（有序或无序）、单链表、二叉查找树、堆等数据结构来实现。

---

为什么选择堆来实现呢？

主要是从时间复杂度来考虑

1. 数组（有序）:插入操作 O(n) 删除操作 O(1)
2. 数组（无序）:插入操作 O(1) 删除操作 O(n)
3. 单链表:        插入操作 O(1)(往表头插) 删除操作 O(n)
4. 二叉查找树： 插入操作 O(logn) 删除操作 O(logn)
5. 堆 ---- 同二叉查找树 （但二叉查找树对于删除操作来说，因为总是删除左子树，会造成树的不平衡）

综上所述，选择最小堆来实现优先级队列

---

实现代码:

设数组A[0---n-1]满足堆性质

设Maxsize为队列的最大元素数

void siftup(int A[],int i,int x);

void siftdown(int A[],int i,int n);

1）插入操作：

/*pre:  A[0---n-1]满足堆性质post：插入元素t，使得A[0--n-1,n]同样满足堆性质*/void insert(int A[],int &n,int t){    if(n>=Maxsize)        return;    n++;    A[n-1] = t;    siftup(A,n-1,t);}

2) 删除操作

/*pre:  A[0---n-1]满足堆性质post：删除最小值*/int extractmin(int A[],int &n){    if(n<1)        return ERROR;    int temp = A[0];    swap(A[0],A[n-1]);    n--;    siftdown(A,0,n);    return temp;}