优先队列的定义
例如右图：任务的优先权及执行顺序的关系
优先队列的类定义 #include<assert.h>#include<iostream.h>#include<stdlib.h>constintmaxPQSize=50;//缺省元素个数template<class Type>class PQueue{public: PQueue(); ~PQueue() { delete[]pqelements; } void PQInsert(const Type& item); Type PQRemove(); void makeEmpty() { count=0; } int IsEmpty() const { returncount==0; } intIsFull() const { return count==maxPQSize; } int Length() const { return count; } private: Type *pqelements;//存放数组 int count;//队列元素计数};优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priority queue)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority queue),查找操作用来搜索优先权最大的元素,删除操作用来删除该元素.优先权队列中的元素可以有相同的优先权,查找与删除操作可根据任意优先权进行.
最大优先权队列的抽象数据类型描述如ADT 9-1所示,最小优先队列的抽象数据类型描述与之类似,只需将最大改为最小即可.
ADT 最大优先队列的抽象数据类型描述抽象数据类型
pascal 版本优先队列 vara:array[0..1000]oflongint;l,i,j,x,y,n,m:longint;procedureup(i:longint);//向上调整vart,j:longint;beginj:=i;whilej>1dobeginj:=i>>1;ifa[j]>a[i]thenbegint:=a[j];a[j]:=a[i];a[i]:=t;i:=j;endelsebreak;end;end;proceduredown(i:longint);//向下调整vart,j:longint;beginwhilei<=(l>>1)dobeginj:=2*i;if(j<l)and(a[j+1]<a[j])theninc(j);ifa[i]>a[j]thenbegint:=a[i];a[i]:=a[j];a[j]:=t;i:=j;endelsebreak;end;end;procedurerudui(i:longint);//入队begininc(l);a[l]:=i;up(l);end;functionchudui:longint;//出队vart,j,ans:longint;beginans:=a[1];a[1]:=a[l];a[l]:=0;dec(l);down(1);exit(ans);end;beginreadln(n);l:=n;fori:=1tondoread(a[i]);readln;fori:=n>>1downto1dodown(i);readln(m);fori:=1tomdobeginreadln(x,y);ifx=1thenrudui(y);//将y入队ifx=0thenwriteln(chudui);//探出栈顶元素并调整end;end.
