首先明确优先级队列的两个表象:
能够实现上述两个操作的数据结构-----优先级队列。
我们可以使用数组(有序或无序)、单链表、二叉查找树、堆等数据结构来实现。
为什么选择堆来实现呢?
主要是从时间复杂度来考虑
综上所述,选择最小堆来实现优先级队列
实现代码:
设数组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; }
原文:http://www.cnblogs.com/welsh-android-learning/p/3516370.html