优先级队列-堆

---

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

插入元素删除最小元素

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

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

---

为什么选择堆来实现呢？

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

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

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

---

实现代码:

设数组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; }

 

 

 

转载于:https://www.cnblogs.com/welsh-android-learning/p/3516370.html