優先隊列

例如右圖：任務的優先權及執行順序的關係

優先隊列的類定義

優先隊列是0個或多個元素的集合，每個元素都有一個優先權或值，對優先隊列執行的操作有1) 查找;2) 插入一個新元素;3) 刪除。在最小優先隊列(min priority queue)中，查找操作用來搜索優先權最小的元素，刪除操作用來刪除該元素；對於最大優先隊列(max priority queue),查找操作用來搜索優先權最大的元素，刪除操作用來刪除該元素。優先權隊列中的元素可以有相同的優先權，查找與刪除操作可根據任意優先權進行.

最大優先權隊列的抽象數據類型描述下所示，最小優先隊列的抽象數據類型描述與之類似，只需將最大改為最小即可.

ADT 最大優先隊列的抽象數據類型描述抽象數據類型

pascal 版本優先隊列

有限的元素集合，每個元素都有一個優先權

操作

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，檢查前幾個最高或最低優先順序元素，清除隊列，清除隊列子集，執行批量插入，將兩個或多個隊列合併為一個，增加優先順序任何元素等。

可以將優先順序隊列想象為已修改的隊列，但是當一個人從隊列中獲取下一個元素時，將首先檢索優先順序最高的元素。

堆棧和隊列可以被建模為特定類型的優先順序隊列。提醒一下，堆棧和隊列的行為方式如下：

堆棧 - 元素以最後一個順序被拉入（例如，一疊紙）

隊列 - 元素先進先出（例如，自助餐廳中的一條線）

在堆棧中，每個插入元素的優先順序是單調遞增的；因此，插入的最後一個元素始終是第一個檢索的元素。在隊列中，每個插入元素的優先順序是單調遞減的；因此，插入的第一個元素始終是第一個檢索到的元素。