《数据结构与算法分析》学习笔记-第六章-优先队列
目录
队列中的某些成员有更高的优先级，需要优先执行或者尽快执行完毕
6.1 模型
优先队列允许至少有两种操作的数据结构：
- Insert： 插入元素，相当于入队
- DeleteMin: 找出、返回和删除优先队列中最小的元素，相当于出队
6.2 简单实现
- 链表实现：
- 单链表，Insert:从头插入，DeleteMin:遍历整个链表找到最小单元返回并删除
- 单链表，Insert:按大小顺序插入，DeleteMin: 删除链表第一个元素（最小）即可。
一般来讲，第一个方案实际上要比第二个方案效率高。因为DeleteMin操作不多于删除操作次数的事实
- 二叉查找树：Insert & DeleteMin 平均运行时间都是O(logN),如果一直删除最小元素，那么右子树会明显加重，变得不平衡。而且查找树支持许多优先队列并不需要的操作
- 二叉堆：使用基本的数据结构不需要指针，以最坏情形时间O(logN)支持Insert & DeleteMin。Insert实际花费常数平均时间，若无删除干扰，该结构的实现将以线性时间建立一个具有N项的优先队列。合并的实现则需要指针
6.3 二叉堆
堆具有结构性和堆序性，而对堆的一次操作可能会破坏这两个性质，因此堆的操作必须要到堆的所有性质都被满足时才能停止
6.3.1 结构性质
- 堆是一棵被完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树又叫完全二叉树
- 一棵高为h的完全二叉树有2h到2(h+1) – 1个节点，这意味着，完全二叉树的高是logN，显然它是O(logN)
- 完全二叉树很有规律，可以用一个数组表示而不需要指针。对于数组中任一位置i上的元素，其左儿子在位置2i上，右儿子在左儿子后的单元(2i + 1)上，它的父亲则在位置[i/2]上。遍历该树所需要的操作也极其简单，在大部分计算机上运行很快。这种实现方法的唯一问题在于，最大的堆大小需要实现估计，但对于典型的情况这不成问题
- 一个堆将由一个数组（不论关键字类型），一个代表最大值的整数以及当前的堆大小组成
6.3.2 堆序性质
- 在一个堆中，对于每一个节点X，X的父亲中的关键字小于（或等于）X中的关键字，根节点除外（它没有父亲）。
- 根据堆序性质，最小元总可以在根处找到
6.3.3 实现
- 节点定义
typedef struct PriorityQueueNode {
int Capacity;
int Size;
ElementType *Elements;
} PriorityQueueNode_T;
typedef PriorityQueueNode_T *PtrToPriorityQueue;
- Initialize
PtrToPriorityQueue
Initialize(int MaxElements)
{
PtrToPriorityQueue Q = NULL;
Q = (PtrToPriorityQueue)malloc(sizeof(struct PriorityQueueNode));
if (Q == NULL) {
printf("Q malloc failed\n");
return NULL;
}
memset(Q, 0, sizeof(struct PriorityQueueNode));
Q->Capacity = MaxElements;
Q->Size = 0;
Q->Elements = (ElementType *)malloc(sizeof(ElementType) * (Q->Capacity + 1));
if (Q->Elements == NULL) {
if (Q != NULL) {
printf("Q->Elements malloc failed\n");
free(Q);
}
}
memset(Q->Elements, 0, sizeof(ElementType) * (Q->Capacity + 1));
Q->Elements[0] = MINKEYVALUE;
return Q;
}
- Insert
void
Insert(PtrToPriorityQueue Q, ElementType X)
{
if (IsFull(Q)) {
printf("PtrToPriorityQueue is full\n");
return;
}
int cnt;
for (cnt = ++Q->Size; Q->Elements[cnt / 2] > X; cnt /= 2) {
Q->Elements[cnt] = Q->Elements[cnt / 2];
}
Q->Elements[cnt] = X;
}
- DeleteMin，时间复杂度平均为O(logN)
ElementType
DeleteMin(PtrToPriorityQueue Q)
{
if (IsEmpty(Q)) {
printf("PtrToPriorityQueue is empty\n");
return Q->Elements[0];
}
int cnt, Child;
ElementType MinKeyValue = Q->Elements[1];
ElementType LastKeyValue = Q->Elements[Q->Size--];
for (cnt = 1; 2 * cnt <= Q->Size; cnt = Child) {
Child = 2 * cnt;
if (Child < Q->Size && Q->Elements[Child] > Q->Elements[Child + 1]) {
Child++;
}
if (LastKeyValue > Q->Elements[Child]) {
Q->Elements[cnt] = Q->Elements[Child];
} else {
break;
}
}
Q->Elements[cnt] = LastKeyValue;
return MinKeyValue;
}
6.3.4 其他的堆操作
- 按照最小元设计的堆在求最大元方面没有任何帮助
- 一个堆所蕴含的关于序的信息很少
- 假设通过某种方法得知每个元素的位置，那么有几种其他操作的开销将变小
- DecreaseKey降低关键字的值: DecreaseKey(P, X, H)操作降低在位置P处的关键字的值。降值的幅度为正的量X。由于这可能破坏堆的序，必须通过上滤堆进行调整。例如系统管理程序能够使它们的程序以最高优先级进行
- IncreaseKey增加关键字的值：IncreaseKey(P, X, H)操作增加位置P处关键字的值，增加的幅度为量X。可以用下滤来完成。许多调度程序自动的降低过多消耗CPU时间的进程的优先级
- Delete删除：Delete(P, H)操作删除堆中位置P上的节点。通过首先执行DecreaseKey(P, 无穷， H)，然后再执行DeleteMin(H)来完成。当一个进程被用户终止（而不是正常终止）时，它必须从优先队列中除去
- BuildHeap构建堆：N个关键字作为输入并把它们放入空堆中。可以使用N个Insert操作来完成，每个Insert将花费O(1)平均时间，以及O(NlogN)最坏情形时间，因此该算法的总的运行时间则是O(N)平均时间而不是O(NlogN)最坏情形时间。该指令能够以线性平均时间实施。
for (i = N / 2; i > 0; i--) { PercolateDown(i); }- 定理：包含2^(b + 1) – 1个节点的高为b的理想二叉树的节点的高度的和为2^(b + 1) – 1 – (b + 1)
6.4 优先队列的应用
优先队列可以有效地用于几个图论算法的实现中
6.4.1 选择问题
- 算法6A：求N个输入元素中，第k个最小的元素。首先以O(N)时间创建堆，随后，执行k-1次DeleteMin，第k次取出的元素即为第k小的元素。由于每次DeleteMin用时O(logN)，有k次DeleteMin，因此总的运行时间是O(N + klogN)。如果k = O(N/logN)，那么运行时间取决于BuildHeap操作，即O(N)。对于大的k值，运行时间为O(klogN)，如果k = [N/2],那么运行时间则为Θ(NlogN)。如果对k = N运行该程序并在元素离开堆时记录它们的值，那么实际上已经对输入文件以O(NlogN)做了排序，即堆排序
- 算法6B：在任一时刻，我们都将维持k个最大元素的集合S。在前k个元素读入以后，当再读入一个新元素时，该元素将与第k个最大元素进行比较，记这第k个最大的元素为Sk，注意S0是S中最小的元素，如果新的元素更大，那么用心元素代替S中的Sk。此时，S将有一个新的最小元素，它可能就是新添加进的元素，也可能不是。在输入终了时，我们找到S中的最小元素将其返回，就是答案。前k个元素，调用一次BuildHeap以总时间O(k)被置入堆中。处理每个其余的元素的时间为O(1)，即检测元素是否进入S。再加上时间O(logk)(在必要时删除Sk并插入新元素)，因此总的时间是O(k + (N-k)logk) = O(Nlogk)。该算法也给出中位数的时间界Θ(NlogN)
6.4.2 事件模拟
如果有C个顾客（2C个事件）和k个出纳员，那么模拟的运行时间将会是O(Clog(k + 1))，因为计算和处理每个事件花费O(logH)，其中H = K + 1为堆的大小
6.5 d-堆
- d-堆是二叉堆的简单推广，它像一个二叉堆，只是所有的节点都有d个儿子（因此，二叉堆是2-堆）。d-堆将Insert操作的运行时间改进为O(log(d)N)，然而对于大d，DeleteMin操作费时得多，因为虽然树浅了，但是d个儿子中的最小者是必须要找出的，如使用标准的算法，会花费d – 1次比较，于是将次操作的用时提高到O(dlog(d)N)
- 因为存在许多算法，其插入次数比DeleteMin的次数多很多，因此理论上的加速是可能的。当优先队列太大不能完全装入贮存的时候，d-堆也是有用的，这种情况下d-堆能够以与B-树大致相同的方式发挥作用。实践中4-堆可以胜过二叉堆。d-堆将两个堆合成一个堆是困难的操作（Merge）
6.6 左式堆
- 设计一种堆结构像二叉堆那样高效的支持合并操作，即以O(N)时间处理一次merge。而且只使用一个数组很困难，因为合并似乎需要把一个数组拷贝到另一个数组中去，对于相同大小的堆将花费时间Θ（N）。
- 所有支持高效合并的高级数据结构都需要使用指针，预计这将使得所有其他的操作变慢，处理指针一般比用2做乘法和除法更耗费时间
- 左式堆也具有结构特性和有序性。左式堆具有相同的堆序性质。左式堆也是二叉树，左式堆和二叉树唯一的区别是：左式堆不是理想平衡的，而实际上是趋于非常不平衡
6.6.1 左式堆的性质
- 我们把任一节点X的零路径长（NPL）Npl(X)定义为从X到一个没有两个儿子的节点的最短路径的长。因此，具有0个或1个儿子的节点的Npl为0，而Npl(NULL) = -1
- 任一节点的零路径长比它的诸儿子节点的零路径长的最小值多1，这个结论也适用于少于两个儿子的节点，因为NULL的零路径长是-1
- 左式堆的性质是：对于堆中每一个节点X，左儿子的零路径长至少与右儿子的零路径长一样大。显然更偏重于使树向左增加深度。确实有可能存在由左节点形成的长路径构成的树（而且实际上更便于合并操作），因此，我们有了左式堆这个名称
- 因为左式堆趋向于加深左路径，所以右路径应该短。事实上，沿左式堆的右路径确实是该堆中最短的路径。否则就会存在一条路径通过某个节点X并取得左儿子，此时X破坏了左式堆的性质
- 定理6.2：在右路径上由r个节点的左式树，必然至少有2^r – 1个节点
- N个节点的左式树有一条右路径最多含有log(N+1)个节点，对左式堆操作的一般思路是将所有的工作放到右路径上进行，它保证树深短。对右路径的Insert和Merge可能会破坏左式堆性质，但是易于回复该性质
6.6.2 左式堆的操作
对左式堆的基本操作是合并。插入只是合并的特殊情形，因此我们可以把插入看成是单节点堆与一个大的堆的Merge。
- 节点定义
struct TreeNode {
ElementType Element;
PriorityQueue Left;
PriorityQueue Right;
}
6.7 斜堆
- 斜堆是左式堆的自调节形式，实现起来极其简单。斜对是有堆序的二叉树，但是不存在对树的结构限制。
- 不同于左式堆，关于任意节点的零路径长的任何信息都不保留。斜堆的右路径在任何时刻都可以任意长，所有操作的最坏情形运行时间均为O(N)
- 任意M次连续操作，总的最坏情形运行时间是O(MlogN)。因此每次操作的摊还时间为O(logN)
- 斜堆的基本操作也是合并操作。这个Merge例程还是递归的，我们执行与之前完全相同的操作，只有一个例外: 对于左式堆，我们查看是否左儿子和右儿子满足左式堆堆序性质并交换那些不满足该性质者；但对于斜堆，除了这些右路径上所有结点的最大者不交换他们的左右儿子外，交换是无条件的。这个例外就是在自然递归实现时所发生的现象，因此它实际上根本不是特殊情形。由于该节点肯定没有右儿子，因此执行交换是愚蠢的
- 我们也可像左式堆那样非递归地进行所有的操作：合并右路径，除最后的节点外交换右路径上每个结点的左儿子和右儿子。由于除去右路径上最后节点外的所有节点都将它们的儿子交换，因此最终结果是它变成了新的左路径
6.8 二项队列
左式堆和斜堆每次操作花费O(logN)实践。有效的支持了合并、插入和DeleteMin。因为二叉堆每次操作花费常数平均时间支持插入。二项队列支持所有这三种操作，每次操作的最坏情形运行时间为O(logN)，而插入操作花费常数时间
6.8.1 二项队列结构
- 一个二项队列不是一棵堆序的树，而是堆序树的集合，称为森林。堆序树中的每一棵都是有约束的形式，叫做二项树。每一个高度上至多存在一棵二项树。高度为0的二项树是一颗单节点树，高度为k的二项树Bk通过将一棵二项树Bk-1附接到另一棵二项树Bk-1的根上而构成。高度为k的二项树恰好有2^k个节点，而在深度为d处的节点数是二项系数。
- 如果我们把堆序施加到二项树上并允许任意高度上最多有一棵二项树，那么我们能够用二项树的集合唯一地表示任意大小的优先队列。例如，大小为13的优先队列可以用森林B3，B2，B0表示，我们可以把这种表示写成1101，它不仅以二进制表示了13，而且也表示这样的事实：在上述表示中，B3，B2，B0出现，B1则没有
6.8.2 二项队列的操作
- 最小元可以通过搜索所有的树的根来找出。由于最多有logN棵不同的树，因此最小元可以在时间O(logN)找到。另外，如果记住最小元在其他操作期间变化时更新它，那么我们可以保留最小元的信息并以O(1)时间执行该操作
- 合并操作基本上是通过将两个队列加到一起来完成的。两个队列中，相同高度的二项树相加。高度从低到高，即从0开始。最坏情形花费时间O(logN)
- 插入操作就是特殊情形的合并。只需创建一棵单节点树并执行一次合并。最坏情形运行时间是O(logN)对一个初始为空的二项队列进行N次Insert将花费的最坏情形时间为O(N).事实上，只用N-1次比较就有可能进行该操作。谨记一点：Bk树是由两棵Bk-1树组成的。因此，插入一定是按照这个原则进行的。
- DeleteMin可以通过首先找出一棵具有最小根的二项树来完成，令该树为Bk，并令原始的优先队列为H。我们从H的树的森林中除去二项树Bk，形成新的二项树队列H’。Bk不要扔掉，除去Bk的根，得到一些二项树B0, B1, …, Bk-1，它们共同形成优先队列H”。合并H’和H”，操作结束。为了找出含有最小元素的树创建队列H’和H”花费时间O(logN)。合并这连个队列又花费O(logN)时间。整个DeleteMin操作花费时间O(logN)
6.8.3 二项队列的实现
DeleteMin操作需要快速找出根的所有子树的能力，因此，需要一般树的表示方法：每个结点的儿子都存在一个链表中，而且每个节点都有一个指向它的第一个儿子（如果它有的话）的指针。还要求，诸儿子按照它们的子树的大小排序。需要保证能够很容易的合并两棵树。当两棵树被合并时，其中一棵树作为儿子被加到另一棵树上。由于这棵新树将是最大的子树，因此，以大小递减的方式保持这些子树事有意义的。只有这时，我们才能有效地合并两颗二项树，从而合并两个二项队列。二项队列将是二项树的数组。总之，二项树的每一个节点将包含数据、第一个儿子以及右兄弟。二项树中的诸儿子以递减次序排列
- 节点定义
typedef struct BinNode *Position;
typedef struct Collection *BinQueue;
struct BinNode
{
ElementType Element;
Position LeftChild;
Position NextSibling;
}
struct Collection
{
int CurrentSize;
BinTree TheTrees[MaxTrees];
}
- CombineTree
BinTree
Merge(BinTree T1, BinTree T2)
{
if (T1->Element > T2->Element) {
return Merge(T2, T1);
}
T2->NextSibling = T1->LeftChild;
T1->LeftChild = T2;
return T1;
}
- Merge
BinQueue
Merge(BinQueue H1, BinQueue H2)
{
BinTree T1, T2, Carry = NULL;
int i, j;
if (H1->CurrentSize + H2->CurrentSize > Capacity) {
printf("Merge would exceed capacity\n");
}
H1->CurrentSize += H2->CurrentSize;
for (i = 0; j = 1; j <= H1->CurrentSize; i++, j*= 2) {
T1 = H1->TheTrees[i];
T2 = H2->TheTrees[i];
switch(!!T1 + 2 * !!T2 + 4 * !!Carry) {
case 0: /* No trees */
case 1: /* Only H1 */
break;
case 2: /* Only H2 */
H1->TheTrees[i] = T2;
H2->TheTrees[i] = NULL;
break;
case 4: /* Only Carry */
H1->TheTrees[i] = Carry;
Carry = NULL;
break;
case 3: /* H1 and H2 */
Carry = CombineTrees(T1, T2);
H1->TheTrees[i] = H2->TheTrees[i] = NULL;
break;
case 5: /* H1 and Carry */
Carry = CombineTrees(T1, Carry);
H1->TheTrees[i] = NULL;
break;
case 6: /* H2 and Carry */
Carry = CombineTrees(T2, Carry);
H2->TheTrees[i] = NULL;
break;
case 7: /* All three */
H1->TheTrees[i] = Carry;
Carry = CombineTrees(T1, T2);
H2->TheTrees[i] = NULL;
break;
}
}
return H1;
}
- DeleteMin
ElementType
DeleteMin(BinQueue H)
{
int i, j;
int MinTree;
BinQueue DeletedQueue;
Position DeletedTree, OldRoot;
ElementType MinItem;
if (IsEmpty(H)) {
printf("Empty binomial queue\n");
return -Infinity;
}
MinTtem = Infinity;
for (i = 0; i < MaxTrees; i++) {
if (H->TheTrees[i] && H->TheTrees[i]->Element < MinItem) {
/* Update minimum */
MinItem = H->TheTrees[i]->Element;
MinTree = i;
}
}
DeletedTree = H->TheTrees[MinTree];
OldRoot = DeletedTree;
DeletedTree = DeletedTree->LeftChild;
free(OldRoot);
DeletedQueue = Initialize();
DeletedQueue->CurrentSize = (1 << MinTree) - 1;
for (j = MinTree - 1; j >= 0; j--)
{
DeletedQueue->TheTrees[j] = DeletedTree;
DeletedTree = DeletedTree->NextSibling;
DeletedQueue->TheTrees[j]->NextSibling = NULL;
}
H->TheTrees[MinTree] = NULL;
H->CurrentSize -= DeletedQueue->CurrentSize + 1;
Merge(H, DeletedQueue);
return MinItem;
}
参考文献
- Mark Allen Weiss.数据结构与算法分析[M].America, 2007
本文作者: CrazyCatJack
本文链接: https://www.cnblogs.com/CrazyCatJack/p/13340038.html
版权声明:本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
关注博主:如果您觉得该文章对您有帮助，可以点击文章右下角推荐一下，您的支持将成为我最大的动力！
版权声明：本文为CrazyCatJack原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。