-
優先隊列
鎖定
優先隊列(priority queue)
普通的隊列是一種先進先出的數據結構，元素在隊列尾追加，而從隊列頭刪除。在優先隊列中，元素被賦予優先級。當訪問元素時，具有最高優先級的元素最先刪除。優先隊列具有最高級先出 （first in, largest out）的行為特徵。通常採用堆數據結構來實現。
- 中文名
- 優先隊列
- 外文名
- priority queue
- 特 點
- 元素被賦予優先級
- 類 型
- 數據結構
- 定 義
- 一種先進先出的數據結構，元素在隊列尾追加，而從隊列頭刪除
- 實現方式
- 通常採用堆數據結構
優先隊列定義
例如圖1：任務的優先權及執行順序的關係
圖1 任務的優先權及執行順序的關係
優先隊列的類定義
#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; begin j:=i; while j>1 do begin j:=i>>1; if a[j]>a[i] then begin t:=a[j]; a[j]:=a[i]; a[i]:=t; i:=j; end else break; end; end; procedure down(i:longint);//向下調整 var t,j:longint; begin while i<=(l>>1) do begin j:=2*i; if (j<l)and(a[j+1]<a[j]) then inc(j); if a[i]>a[j] then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; i:=j; end else break; end; end; procedure rudui(i:longint);//入隊 begin inc(l); a[l]:=i; up(l); end; function chudu(i:longint);//出隊 var t,j,ans:longint; begin ans:=a[1]; a[1]:=a[l]; a[l]:=0; dec(l); down(1); exit(ans); end; begin readln(n); l:=n; for i:=1to n do read(a[i]); readln; for i:=n>>1 downto 1do down(i); readln(m); for i:=1 to m do begin readln(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”
[1]
。
此外，peek（在此上下文中通常稱為find-max或find-min）返回最高優先級元素但不修改隊列，它經常被實現，並且幾乎總是在O（1）時間內執行。此操作及其O（1）性能對於許多優先級隊列應用程序至關重要。
更高級的實現可能支持更復雜的操作，例如pull_lowest_priority_element，檢查前幾個最高或最低優先級元素，清除隊列，清除隊列子集，執行批量插入，將兩個或多個隊列合併為一個，增加優先級任何元素等。
優先隊列與隊列相似
可以將優先級隊列想象為已修改的隊列，但是當一個人從隊列中獲取下一個元素時，將首先檢索優先級最高的元素。
堆棧和隊列可以被建模為特定類型的優先級隊列。提醒一下，堆棧和隊列的行為方式如下：
堆棧 - 元素以最後一個順序被拉入（例如，一疊紙）
隊列 - 元素先進先出（例如，自助餐廳中的一條線）
在堆棧中，每個插入元素的優先級是單調遞增的;因此，插入的最後一個元素始終是第一個檢索的元素。在隊列中，每個插入元素的優先級是單調遞減的;因此，插入的第一個元素始終是第一個檢索到的元素。
- 參考資料
-
- 1. 基於K叉樹的優先隊列 ．萬方[引用日期2018-08-06]
