大数据

当前位置:首页 > 大数据

《算法导论》第六章 续

6.5 优先队列

堆排序是一个优秀的算法,但是在实际应用中,第7章将要介绍的快速排序的性能一般会 优于堆排序。尽管如此,堆这一数据结构仍然有很多应用。在这一节中,我们要介绍堆的一个常见应用:作为高效的优先队列。和堆一样,优先队列也有两种形式:最大优先队列和最小优先队列。这里,我们关注于如何基于最大堆实现最大优先队列。练习6. 5-3将会要求读者编写最小优先队列过程。

优先队列( priority queue)是一种用来维护由一组元素构成的集合S的数据结构,其中的每一个元素都有一个相关的值,称为关键字(key)。一个最大优先队列支持以下操作:

INSERT(S, x):把元素x插人集合S中。这一操作等价于S=SU{x}。

MAXIMUM(S):返回S中具有最大键字的元素。

EXTRACT-MAX(S):去掉并返回S中的具有最大键字的元素。

INCREASE-KEY(S, x, k):将元素x的关键字值增加到k,这里假设k的值不小于x的原关键字值。

最大优先队列的应用有很多,其中一个就是在共享计算机系统的作业调度。最大优先队列记录将要执行的各个作业以及它们之间的相对优先级。当一个作业完成或者被中断后,调度器调用EXTRACT-MAX从所有的等待作业中,选出具有最高优先级的作业来执行。在任何时候,调度器可以调用INSERT把一个新作业加入到队列中来。

相应地,最小优先队列支持的操作包括INSERT、MINIMUM、EXTRACT-MIN 和DECREASE-KEY。最小优先队列可以被用于基于事件驱动的模拟器。队列中保存要模拟的事件,每个事件都有一个发生时间作为其关键字。事件必须按照发生的时间顺序进行模拟,因为某

一事件的模拟结果可能会触发对其他事件的模拟。在每一步,模拟程序调用EXTRACT-MIN来选择下一个要模拟的事件。当一个新事件产生时,模拟器通过调用INSERT将其插入最小优先级队列中。在第23章和第24章的内容中,我们将会看到最小优先队列的其他用途,特别是对

DECREASE-KEY操作的使用。

显然,优先队列可以用堆来实现。对一个像作业调度或事件驱动模拟器这样的应用程序来说,优先队列的元素对应着应用程序中的对象。通常,我们需要确定哪个对象对应一个给定的优先队列元素,反之亦然。因此,在用堆来实现优先队列时,需要在堆中的每个元素里存储对应对象的句柄(handle)。句柄(如一个指针或一个整型数等)的准确含义依赖于具体的应用程序。同样,在应用程序的对象中,我们也需要存储一个堆中对应元素的句柄。通常,这一句柄是数组的下标。由于在堆的操作过程中,元素会改变其在数组中的位置,因此,在具体的实现中,在重新确定堆元素位置时,我们也需要更新相应应用程序对象中的数组下标。因为对应用程序对象的访问细节强烈依赖于应用程序及其实现方式,所以这里我们不做详细讨论。需要强调的是,这些句柄也需要被正确地维护。

现在,我们来讨论如何实现最大优先队列的操作。过程HEAP-MAXIMUM可以在Θ(1)时间内实现MAXIMUM操作。

QQ截图20220509112202.jpg

过程HEAP-EXTRACT-MAX实现EXTRACT-MAX操作。它与HEAPSORT过程中的for循环体部分(第3~5行)很相似。

QQ截图20220509112246.jpg

HEAP-EXTRACT-MAX的时间复杂度为O(lgn)。因为除了时间复杂度为O(lgn)的MAX-HEAPIFY以外,它的其他操作都是常数阶的。

HEAP-INCREASE-KEY能够实现INCREASE-KEY操作。在优先队列中,我们希望增加关键字的优先队列元素由对应的数组下标i来标识。这一操作需要首先将元素A[i]的关键字更新为新值。因为增大A[i]的关键字可能会违反最大堆的性质,所以上述操作采用了类似于2.1节

INSERTION-SORT中插入循环(算法第5~7行)的方式,在从当前结点到根结点的路径上,为新增的关键字寻找恰当的插入位置。在HEAP INCREASE-KEY的操作过程中,当前元素会不断地与其父结点进行比较,如果当前元素的关键字较大,则当前元素与其父结点进行交换。这一过程会不断地重复,直到当前元素的关键字小于其父结点时终止,因为此时已经重新符合了最大堆的性质。(准确的循环不变量表示见练习6. 5-5。)

QQ截图20220509112446.jpg

QQ截图20220509112456.jpg

图6-5显示了HEAP-INCREASE-KEY的一个操作过程。在包含n个元素的堆上,HEAP-INCREASE-KEY的时间复杂度是O(lgn)。这是因为在算法第3行做了关键字更新的结点到根结点的路径长度为O(lgn)。

QQ截图20220509112557.jpg

图6-5 HEAP- INCREASE-KEY的操作过程。(a)图 6-4(a)中的量大堆,其中下标为i的结点以深色阴影显示。(b)该结点的关键字增加到15。(c)经过第 4~6行的while循环的一次迭代,该结点与其父结点交换关键字,同时下标i的指示上移到其父结点。(d)经过再一次迭代后得到的最大堆。此时,A[PARENT(i)]≥A[i]。现在,最大堆的性质成立,程序终止

MAX- HEAP-INSERT能够实现INSERT操作。它的输入是要被插入到最大堆A中的新元素的关键字。MAX HEAP-INSERT首先通过增加一个关键字为-∞的叶结点来扩展最大堆。然后调用HEAP-INCREASE-KEY为新结点设置对应的关键字,同时保持最大堆的性质。

QQ截图20220509112749.jpg

在包含n个元素的堆上,MAX-HEAP-INSERT的运行时间为O(lgn)。总之,在一个包含n个元素的堆中,所有优先队列的操作都可以在O(lgn)时间内完成。


练习

6.5-1  试说明 HEAP-EXTRACT-MAX在堆A=<15,13,9,5, 12, 8,7, 4, 0,6,2,1>上的操作过程。

6.5-2  试说明MAX-HEAP-INSERT(A, 10)在堆A=<15, 13,9, 5, 12, 8, 7, 4, 0, 6, 2, 1>上的操作过程。

6.5-3  要求用最小堆实现最小优先队列,请写出HEAP-MINIMUM、HEAP-EXTRACT-MIN、HEAP-DECREASE-KEY和MIN-HEAP-INSERT的伪代码。

6.5-4  在MAX-HEAP-INSERT的第2行,为什么我们要先把关键字设为一∞,然后又将其增加到所需的值呢?

6.5-5  试分析在使 用下列循环不变量时,HEAP-INCREASE-KEY 的正确性:在算法的第4~6行while循环每次迭代开始的时候,子数组A[1.. A. heap-size ]要满足最大堆的性质。如果有违背,只有一个可能:A[i]大于A[PARENT(i)]这里,你可以假定在调用HEAP-INCREASE-KEY时,A[1.. A. heap-size ]是满足最大堆性质的。

6.5-6  在HEAP-INCREASE-KEY的第5行的交换操作中,一般需要通过三次赋值来完成。想一想如何利用INSERTION-SORT内循环部分的思想,只用一次赋值就完成这一交换操作?

6.5-7  试说明如何使用优先队列来实现一个先进先出队列,以及如何使用优先队列来实现栈。(队列和栈的定义见10.1节。)

6.5-8  HEAP-DELETE(A, i)操作能够将结点i从堆A中删除。对于一个包含n个元素的堆,请设计一个能够在O(lgn)时间内完成的HEAP-DELETE操作。

6.5-9  请设计一个时间复杂度为O(n lgk)的算法,它能够将k个有序链表合并为一个有序链表,这里n是所有输人链表包含的总的元素个数。(提示:使用最小堆来完成k路归并。)


思考题

6-1  (用插入的方法建堆)我们可以通过反复调用MAX-HEAPINSERT实现向一个堆中插入元素,考虑BUILD-MAX-HEAP的如下实现方式:

QQ截图20220509113251.jpg

a.当输入数据相同的时候,BUILD-MAX-HEAP和BUILD-MAX-HEAP生成的堆是否总是一样?如果是,请证明;否则,请举出一个反例。

b.证明:在最坏情况下,调用BUILD-MAX-HEAP' 建立一个包含n个元素的堆的时间复杂度是Θ(nlgn)。

6-2  (对d叉堆的分析) d 叉堆与二叉堆很类似,但(一个可能的例外是)其中的每个非叶结点有d个孩子,而不是仅仅2个。

a.如何在一个数组中表示一个d叉堆?

b.包含n个元素的d叉堆的高度是多少?请用n和d表示。

c.请给出EXTRACT-MAX在d叉最大堆上的一个有效实现,并用d和n表示出它的时间复杂度。

d.给出INSERT在d叉最大堆上的一个有效实现,并用d和n表示出它的时间复杂度。

e.给出INCREASE-KEY(A, i, k)的一个有效实现。当k<A[i]时,它会触发一个错误,否则执行A[i]=k,并更新相应的d叉最大堆。请用d和n表示出它的时间复杂度。

6-3  (Young 氏矩阵)在 一个m×n的Young氏矩阵( Young tableau)中,每一行的数据都是从左到右排序的,每一列的数据都是从上到下排序的。Young 氏矩阵中也会存在一些值为∞的数据项,表示那些不存在的元素。因此,Young 氏矩阵可以用来存储r≤mn个有限的数。

a.画出一个包含元素为{9,16, 3,2, 4, 8,5, 14,12}的4×4Young氏矩阵。

b.对于一个m×n的Young氏矩阵Y来说,请证明:如果Y[1, 1]=∞,则Y为空;如果Y[m, n]<∞,则Y为满(即包含mn个元素)。

c. 请给出一个在m×n Young氏矩阵上时间复杂度为O(m+n)的EXTRACT-MIN的算法实现。你的算法可以考虑使用一个递归过程,它可以把一个规模为m×n的问题分解为规模为(m- 1)×n或者m×(n-1)的子问题(提示:考虑使用MAX-HEAPIFY)。这里,定义T(p)用来表示EXTRACT-MIN在任一 m×n的Young氏矩阵上的时间复杂度,其中p=m+n。给出并求解T(p)的递归表达式,其结果为O(m+n)。

d.试说明如何在O(m+n)时间内,将一个新元素插入到一个未满的m×n的Young氏矩阵中。

e.在不用其他排序算法的情况下,试说明如何利用一个n×n的Young氏矩阵在O(n3)时间内将n2个数进行排序。

f.设计一个时间复杂度为O(m+n)的算法,它可以用来判断一个给定的数是否存储在m×n的Young氏矩阵中。


相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~