優先佇列的類定義
優先權佇列 是不同於先進先出佇列的另一種佇列。每次從佇列中取出的是具有最高優先權的元素。
#include <assert.h>
#include <iostream.h>
$include <stdlib.h>
const int maxPQSize = 50; //預設元素個數
template <class Type> class PQueue {
public:
PQueue ( );
~PQueue ( ) { delete [ ] pqelements; }
void PQInsert ( const Type & item );
Type PQRemove ( );
void makeEmpty ( ) { count = 0; }
int IsEmpty ( ) const
{ return count == 0; }
int IsFull ( ) const
{ return count == maxPQSize; }
int Length ( ) const { return count; }
private:
Type *pqelements; //存放數組
int count; //佇列元素計數
}
優先權
優先佇列是0個或多個元素的集合,每個元素都有一個優先權或值,對優先佇列執行的操作有
1) 查找;
2) 插入一個新元素;
3) 刪除.
在最小優先佇列(min priorityq u e u e)中,查找操作用來搜尋優先權最小的元素,刪除操作用來刪除該元素;對於最大優先佇列(max priority queue),查找操作用來搜尋優先權最大的元素,刪除操作用來刪除該元素.優先權佇列中的元素可以有相同的優先權,查找與刪除操作可根據任意優先權進行.
最大優先權佇列的抽象數據類型描述如ADT 9-1所示,最小優先佇列的抽象數據類型描述與之類似,只需將最大改為最小即可.
ADT 最大優先佇列的抽象數據類型描述抽象數據類型
M a x P r i o r i t y Q u e u e{
實例
有限的元素集合,每個元素都有一個優先權
操作
Create ( ):創建一個空的優先佇列
Size ( ):返回佇列中的元素數目
Max ( ):返回具有最大優先權的元素
I n s e rt (x):將x插入佇列
DeleteMax (x):從佇列中刪除具有最大優先權的元素,並將該元素返回至x
}
優先佇列插入元素的複雜度都是O(lgn)，刪除元素的複雜度是O(1)，所以很快。
另一種描述方法是採用有序線性表,當元素按遞增次序排列,使用鍊表時則按遞減次序排列,這兩種描述方法的刪除時間均為( 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 }
//二叉堆就是優先佇列，hehe（父節點大於子節點）
使用無序數組實現優先權佇列(c++)
#include <iostream>
#include <vector>
class UnorderedArrayQuene
{
public:
UnorderedArrayQuene();
void Push(int value);
int DeleteMaxElement();
bool isEmpty();
protected:
bool less(int i, int j);
void exchange(int i, int j);
protected:
std::vector<int> m_Array;
int N; // number of elements
};
UnorderedArrayQuene::UnorderedArrayQuene()
:N(0)
{
}
void UnorderedArrayQuene::Push(int value)
{
m_Array.push_back(value);
N++;
}
bool UnorderedArrayQuene::less(int i, int j)
{
return m_Array[i]<m_Array[j];
}
void UnorderedArrayQuene::exchange(int i, int j)
{
int swap = m_Array[i];
m_Array[i] = m_Array[j];
m_Array[j] = swap;
}
int UnorderedArrayQuene::DeleteMaxElement()
{
int max = 0;
for (int i = 1; i < N; i++)
if (less(max, i)) max = i;
exchange(max, N-1);
return m_Array[--N];
}
bool UnorderedArrayQuene::isEmpty()
{
return N == 0;
}
int main()
{
UnorderedArrayQuene Q;
Q.Push(6);
Q.Push(9);
Q.Push(8);
Q.Push(2);
while(!Q.isEmpty())
{
std::cout<<Q.DeleteMaxElement()<<",";
}
system("pause");
return 0;
}
套用
堆排序
可以用優先權佇列，堆排序(Heapsort)是指利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是 完全二叉樹。大根堆的要求是每個節點的值都不大於其父節點的值，即 A[PARENT[i]] >= A[i]。在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。
哈夫曼編碼
哈夫曼編碼(Huffman Coding)是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。Huffman於1952年提出一種編碼方法，該方法完全依據字元出現機率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼（有時也稱為霍夫曼編碼）。
大型浮點數集合的和
由於比較小的浮點數和比較大的浮點數相加會損失比較大的精度，所以要在集合中找出兩個比較小的浮點數進行相加。類似哈弗曼編碼。
將很多較小的有序檔案歸併為一個較大的檔案
比如外部排序，這裡也用的到優先權佇列。從多個有序檔案中選擇一個最小的數，正常的簡單做法是掃描多個有序小檔案，記錄最小值。假設有n個有序小檔案，那么時間複雜度就是O（n）。這裡可以用優先權佇列來選擇一個最小的數，時間複雜度為O（nlogn） 具體做法是建立n元堆，extract最小值，然後把該最小值所在的檔案下一個數插入堆中，更新堆。
