優先佇列(priority queue)
普通的佇列是一種先進先出的數據結構，元素在佇列尾追加，而從佇列頭刪除。在優先佇列中，元素被賦予優先權。當訪問元素時，具有最高優先權的元素最先刪除。優先佇列具有最高級先出 （first in, largest out）的行為特徵。通常採用堆數據結構來實現。
基本介紹
- 中文名：優先佇列
- 外文名：priority queue
- 特點：元素被賦予優先權
- 類型：數據結構
定義,實例,操作,與佇列相似,
定義
例如右圖：任務的優先權及執行順序的關係
優先佇列的類定義
#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() { ~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<=(l>>1) dobeginj:=2*i;if (j<l)and(a[j+1]<a[j]) then inc(j);if a[i]>a[j] thenbegint:=a[i];a[i]:=a[j];a[j]:=t;i:=j;end else break;end;end;procedure rudui(i:longint);//入隊begininc(l);a[l]:=i;up(l);end;function chudu(i:longint);//出隊var t,j,ans:longint;beginans:=a[1];a[1]:=a[l];a[l]:=0;dec(l);down(1);exit(ans);end;beginreadln(n);l:=n;for i:=1to n do read(a[i]);readln;for i:=n>>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) < 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，檢查前幾個最高或最低優先權元素，清除佇列，清除佇列子集，執行批量插入，將兩個或多個佇列合併為一個，增加優先權任何元素等。
與佇列相似
可以將優先權佇列想像為已修改的佇列，但是當一個人從佇列中獲取下一個元素時，將首先檢索優先權最高的元素。
堆疊和佇列可以被建模為特定類型的優先權佇列。提醒一下，堆疊和佇列的行為方式如下：
堆疊 - 元素以最後一個順序被拉入（例如，一疊紙）
佇列 - 元素先進先出（例如，自助餐廳中的一條線）
在堆疊中，每個插入元素的優先權是單調遞增的;因此，插入的最後一個元素始終是第一個檢索的元素。在佇列中，每個插入元素的優先權是單調遞減的;因此，插入的第一個元素始終是第一個檢索到的元素。
