[科普中国]-优先队列

优先队列(priority queue)

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。通常采用堆数据结构来实现。

定义例如右图：任务的优先权及执行顺序的关系

优先队列的类定义

#include#include#includeconstintmaxPQSize=50;//缺省元素个数templateclass PQueue{public: PQueue(); ~PQueue() { delete[]pqelements; } void PQInsert(const Type& item); Type PQRemove(); void makeEmpty() { ~PQueue(); count=0; } int IsEmpty() const { return count==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 最大优先队列的抽象数据类型描述抽象数据类型

pascal 版本优先队列

vara:array[0..1000]oflongint;l,i,j,x,y,n,m:longint;procedureup(i:longint);//向上调整vart,j:longint;beginj:=i;while j>1 dobeginj:=i>>1;if a[j]>a[i] thenbegint:=a[j];a[j]:=a[i];a[i]:=t;i:=j;end else break;end;end;procedure down(i:longint);//向下调整var t,j:longint;beginwhile i>1) dobeginj:=2*i;if (j>1 downto 1dodown(i);readln(m);for i:=1 to m dobeginreadln(x,y);if x=1 then rudui(y);//将y入队if x=0 then writeln(chudui);//探出栈顶元素并调整end;end.实例有限的元素集合,每个元素都有一个优先权

操作

Create ( ):创建一个空的优先队列

Size ( ):返回队列中的元素数目

Max ( ):返回具有最大优先权的元素

Insert (x):将x插入队列

DeleteMax (x):从队列中删除具有最大优先权的元素,并将该元素返回至x

}

优先队列插入和删除元素的复杂度都是O(log2n)，所以很快。

另一种描述方法是采用有序线性表,当元素按递增次序排列,使用链表时则按递减次序排列,这两种描述方法的删除时间均为( 1 ),插入操作所需时间为(n).

例：

假设我们对机器服务进行收费.每个用户每次使用机器所付费用都是相同的,但每个

用户所需要服务时间都不同.为获得最大利润,假设只要有用户机器就不会空闲,我们可以把

等待使用该机器的用户组织成一个最小优先队列,优先权即为用户所需服务时间.当一个新的

用户需要使用机器时,将他/她的请求加入优先队列.一旦机器可用,则为需要最少服务时间

(即具有最高优先权)的用户提供服务.

如果每个用户所需时间相同,但用户愿意支付的费用不同,则可以用支付费用作为优先权,

一旦机器可用,所交费用最多的用户可最先得到服务,这时就要选择最大优先队列.

下面是数组实现的二叉堆，其中MAX_SIZE是数组的最大长度；ElementType是其中元素的类型；Priority(x: ElementType) 是一个函数，返回值是元素x的优先级，当然也可以用一个Priority数组来保存每个元素的优先级(在这个打字员问题中就应该用一个数组来保存每个元素的优先级，在这个问题中优先级就是从初始密码转换到该密码所需的操作的数目)。

type

PriorityQueue = record

contents: array [1..MAX_SIZE]of ElementType;

last : integer;

end;

{ 将一个优先队列变空 }

procedure MakeNull(var A: PriorityQueue);

begin

A.last := 0;

end;

{ 向优先队列A中插入一个元素x }

procedure Insert(x: ElementType; var A: PriorityQueue);

var

i: integer;

temp:ElementType;

begin

if A.last = MAX_SIZE then

Error('Priority Queue is full.')

else begin

A.last := A.last + 1;

A.contents[A.last] := x;

i := A.last;

while (i > 1) and ( Priority(A.contents)

begin

temp := A.contents;

A.contents:= A.contents[i div 2];

A.contents[i div 2] := temp;

i := i div 2;

end; { end of while }

end; { end of else }

end; { end of Insert }

{ 删除优先队列对头的那个优先级最小的元素，并将其值返回 }

function DeleteMin(var A: PriorityQueue): ElementType;

var

minimun : ElementType;

i : integer;

begin

if A.last = 0 then

Error('Priority Queue is empty. ')

else begin

minimun := A.contents[1];

A.contents[1] := A.contents[A.last];

A.last := A.last - 1;

i := 1;

while i

begin

if (Priority(A.contents[2*i])

then j := 2*i;

else j := 2*i + 1;

{ j节点是i节点具有较高优先级的儿子，当i节点只有一个儿子的时候，j节点是i节点的唯一儿子 }

if Priority(A.contents) > Priority(A.contents[j]) then

begin

temp := A.contents;

A.contents:= A.contents[j];

A.contents[j] := temp;

i := j;

end

else begin { 不能再向下推了 }

DeleteMin := minimum;

exit;

end;

end; { end of while }

{ 这时已经到达叶结点 }

DeleteMin := minimum;

exit;

end; { end of else }

end; { end of DeleteMin }

//二叉堆就是优先队列（父节点大于子节点）

操作优先级队列必须至少支持以下操作：

is_empty：检查队列是否没有元素。

insert_with_priority：使用关联的优先级向队列添加元素。

pull_highest_priority_element：从队列中删除具有最高优先级的元素，并将其返回。

这也称为“pop_element（Off）”，“get_maximum_element”或“get_front（most）_element”。

一些约定颠倒了优先级的顺序，将较低的值视为较高的优先级，因此这也可称为“get_minimum_element”，并且在文献中通常称为“get-min”。

这可以替代地被指定为单独的“peek_at_highest_priority_element”和“delete_element”函数，其可以被组合以产生“pull_highest_priority_element”1。

此外，peek（在此上下文中通常称为find-max或find-min）返回最高优先级元素但不修改队列，它经常被实现，并且几乎总是在O（1）时间内执行。此操作及其O（1）性能对于许多优先级队列应用程序至关重要。

更高级的实现可能支持更复杂的操作，例如pull_lowest_priority_element，检查前几个最高或最低优先级元素，清除队列，清除队列子集，执行批量插入，将两个或多个队列合并为一个，增加优先级任何元素等。

与队列相似可以将优先级队列想象为已修改的队列，但是当一个人从队列中获取下一个元素时，将首先检索优先级最高的元素。

堆栈和队列可以被建模为特定类型的优先级队列。提醒一下，堆栈和队列的行为方式如下：

堆栈 - 元素以最后一个顺序被拉入（例如，一叠纸）

队列 - 元素先进先出（例如，自助餐厅中的一条线）

在堆栈中，每个插入元素的优先级是单调递增的;因此，插入的最后一个元素始终是第一个检索的元素。在队列中，每个插入元素的优先级是单调递减的;因此，插入的第一个元素始终是第一个检索到的元素。

本词条内容贡献者为:

王伟 - 副教授 - 上海交通大学