-
優先級隊列
鎖定
如果我們給每個元素都分配一個數字來標記其優先級，不妨設較小的數字具有較高的優先級，這樣我們就可以在一個集合中訪問優先級最高的元素並對其進行查找和刪除操作了。這樣，我們就引入了優先級隊列 這種數據結構。 優先級隊列（priority queue） 是0個或多個元素的集合，每個元素都有一個優先權，對優先級隊列執行的操作有（1）查找（2）插入一個新元素 （3）刪除 一般情況下，查找操作用來搜索優先權最大的元素，刪除操作用來刪除該元素 。對於優先權相同的元素，可按先進先出次序處理或按任意優先權進行。
- 中文名
- 優先級隊列
- 外文名
- priority queue
- 關鍵詞
- 優先權
- 組 成
- 0個或多個元素集合
優先級隊列優先隊列的類定義
優先級隊列 是不同於先進先出隊列的另一種隊列。每次從隊列中取出的是具有最高優先權的元素。
#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 最大優先隊列的抽象數據類型描述抽象數據類型
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 }
使用無序數組實現優先級隊列(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最小值，然後把該最小值所在的文件下一個數插入堆中，更新堆。
