定義
例如圖1：任務的優先權及執行順序的關系
優先隊列的類定義
#include優先隊列是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<=(l>>1) dobeginj:=2*i;if (j實例
有限的元素集合,每個元素都有一個優先權
操作
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) < Priority(A.contents[i div 2]) do
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 < (A.last div 2) do
begin
if (Priority(A.contents[2*i]) < Priority(A.contents[2*i+1])) or (2*i = A.last)
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”。
此外，peek（在此上下文中通常稱為find-max或find-min）返回最高優先級元素但不修改隊列，它經常被實現，并且幾乎總是在O（1）時間内執行。此操作及其O（1）性能對于許多優先級隊列應用程序至關重要。
更高級的實現可能支持更複雜的操作，例如pull_lowest_priority_element，檢查前幾個最高或最低優先級元素，清除隊列，清除隊列子集，執行批量插入，将兩個或多個隊列合并為一個，增加優先級任何元素等。
與隊列相似
可以将優先級隊列想象為已修改的隊列，但是當一個人從隊列中獲取下一個元素時，将首先檢索優先級最高的元素。
堆棧和隊列可以被建模為特定類型的優先級隊列。提醒一下，堆棧和隊列的行為方式如下：
堆棧 - 元素以最後一個順序被拉入（例如，一疊紙）
隊列 - 元素先進先出（例如，自助餐廳中的一條線）
在堆棧中，每個插入元素的優先級是單調遞增的;因此，插入的最後一個元素始終是第一個檢索的元素。在隊列中，每個插入元素的優先級是單調遞減的;因此，插入的第一個元素始終是第一個檢索到的元素。
