优先级队列
如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样，我们就引入了优先级队列 这种数据结构。 优先级队列(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 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<m_Array[j];
}
void UnorderedArrayQuene::exchange(int i, int j)
{
int swap = m_Array;
m_Array = 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] >= A。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
哈夫曼编码
哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码(有时也称为霍夫曼编码)。
集合的和
由于比较小的浮点数和比较大的浮点数相加会损失比较大的精度，所以要在集合中找出两个比较小的浮点数进行相加。类似哈弗曼编码。
文件归并
比如外部排序，这里也用的到优先级队列。从多个有序文件中选择一个最小的数，正常的简单做法是扫描多个有序小文件，记录最小值。假设有n个有序小文件，那么时间复杂度就是O(n)。这里可以用优先级队列来选择一个最小的数，时间复杂度为O(nlogn) 具体做法是建立n元堆，extract最小值，然后把该最小值所在的文件下一个数插入堆中，更新堆。