内蒙古大学《算法与数据结构》讲义09优先队列

下载第9章优 先 队 列与第6章F I F O结构的队列不同，优先队列中元素出队列的顺序由元素的优先级决定。从优先队列中删除元素是根据优先权高或低的次序，而不是元素进入队列的次序。可以利用堆数据结构来高效地实现优先队列。堆是一棵完全二叉树，可用 8 . 4节所介绍的公式化描述方法来高效存储完全二叉树。在高度和重量上取得平衡的左高树很适合于用来实现优先队列。本章的内容涵盖了堆和左高树。在本章的应用部分，利用堆开发了一种复杂性为O (nl o gn) 的排序算法，称为堆排序。在第2章所介绍的对n 个元素进行排序的算法，其复杂性均为O (n2 )。虽然第3章介绍的箱子排序和基数排序算法的运行时间为(n)，但算法中元素的取值必须在合适的范围内。堆排序是迄今为止所讨论的第一种复杂性优于O (n2 ) 的通用排序算法，第1 4章将讨论另一种与堆排序具有相同复杂性的排序算法。从渐进复杂性的观点来看，堆排序是一种优化的排序算法，因为可以证明，任何通用的排序算法都是通过成对比较元素来获得 (nl o gn) 复杂性的（见1 4 . 4 . 2节） 。本节所考察的另外两个应用是机器调度和生成霍夫曼编码。机器调度问题属于 N P -复杂问题，对于这类问题不存在具有多项式时间复杂性的算法。而第 2章提到的大量事实表明，只有具有多项式时间复杂性的算法才是可行的，因此，经常利用近似算法或启发式算法来解决 N P -完全问题，这些算法能在合理的时间内完成，但并不能保证找到最佳结果。对于机器调度应用，利用堆数据结构获得了有效解决机器调度问题的近似算法。本章没有提供有关左高树的应用，其实6 . 4 . 4节中的工厂仿真在这方面是一个很好的应用。9.1 引言优先队列（priority queue）是0个或多个元素的集合，每个元素都有一个优先权或值，对优先队列执行的操作有1) 查找；2) 插入一个新元素；3) 删除。在最小优先队列（min priorityq u e u e）中，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素；对于最大优先队列（max priority queue） ，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。优先权队列中的元素可以有相同的优先权，查找与删除操作可根据任意优先权进行。最大优先权队列的抽象数据类型描述如 ADT 9-1所示，最小优先队列的抽象数据类型描述与之类似，只需将最大改为最小即可。ADT 9-1 最大优先队列的抽象数据类型描述抽象数据类型M a x P r i o r i t y Q u e u e实例有限的元素集合，每个元素都有一个优先权操作C reate ( )：创建一个空的优先队列Size ( )：返回队列中的元素数目Max ( )：返回具有最大优先权的元素I n s e rt (x)：将x 插入队列DeleteMax (x)：从队列中删除具有最大优先权的元素，并将该元素返回至 x例9-1 假设我们对机器服务进行收费。每个用户每次使用机器所付费用都是相同的，但每个用户所需要服务时间都不同。为获得最大利润，假设只要有用户机器就不会空闲，我们可以把等待使用该机器的用户组织成一个最小优先队列，优先权即为用户所需服务时间。当一个新的用户需要使用机器时，将他 /她的请求加入优先队列。一旦机器可用，则为需要最少服务时间（即具有最高优先权）的用户提供服务。如果每个用户所需时间相同，但用户愿意支付的费用不同，则可以用支付费用作为优先权，一旦机器可用，所交费用最多的用户可最先得到服务，这时就要选择最大优先队列。例9-2 考察6 . 4 . 4节所介绍的工厂仿真问题，对其事件队列所执行的操作有：1）查找具有最小完成时间的机器；2）改变该机器的完成时间。假设我们构造一个最小优先队列，队列中的元素即为机器，元素的优先权为该机器的完成时间。最小优先队列的查找操作可用来返回具有最小完成时间的机器。为了修改此机器的完成时间，可以先从队列中删除具有最小优先权的元素，然后用新的完成时间作为该元素的优先权并将其插入队列。实际上，为了满足事件表的应用，可以在最小优先队列的A D T表中新增加一个操作，用来修改具有最小优先权元素的优先权。最大优先队列也可用于工厂仿真问题。在6 . 4 . 4节中的仿真程序中，每台机器按先进先出的方式来完成等待服务的任务，因此可以为每台机器配置了一个 F I F O队列。但如果将服务规则改为“一旦机器可用，则从等待任务中选择优先权最大的任务进行处理” ，每台机器就需要一个最大优先队列。每台机器执行的操作有： 1）每当一个新任务到达，将其插入该机器的最大优先队列中；2）一旦机器可以开始运行一个新任务，将具有最大优先权的任务从该机器的队列中删除，并开始执行它。当每个机器的服务规则如上述改变之后，则需用一个最小优先队列来表示仿真问题中的事件表，用一个最大优先队列来存储每台机器旁的等待任务。在 6 . 4 . 4节的仿真模型中我们事先已经知道事件表的长度，即机器的台数，并且在整个仿真过程中事件表的长度不会改变，所以可采用一个公式化描述的优先权队列来表示时间表。但更常见的是必须考虑加入新机器或移走旧机器的情况，所以最好使用链表描述的优先队列，这样在队列建立时就不必事先预测队列的最大长度，也不必动态地改变数组的大小。如同在6 . 4 . 4节中选择链表F I F O队列而不是公式化队列一样，每个机器的优先权队列也最好是链表队列。每个机器的队列长度在仿真过程中不断变化，而所有队列的长度之和却总是等于未完成的任务数之和。本章提供了优先权队列有效的描述方法。鉴于最大优先队列与最小优先队列十分类似，故在此只明确给出了最大优先队列的描述。9.2 线性表描述最大优先队列最简单的方法是采用无序线性表。假设有一个具有n 个元素的优先队列，如果利用公式（2 - 1） ，那么插入操作可以十分容易地在表的右端末尾执行，插入所需时间为( 1 )。删除操作时必须查找优先权最大的元素，即在未排序的n 个元素中查找具有最大优先权的元素，所以删除操作所需时间为(n)。如果利用链表，插入操作在链头执行，时间为( 1 )，第9章优 先 队 列2 7 7下载而每个删除操作所需时间为(n)。另一种描述方法是采用有序线性表，当使用公式（ 2 - 1）时元素按递增次序排列，使用链表时则按递减次序排列，这两种描述方法的删除时间均为( 1 )，插入操作所需时间为(n)。练习1. 利用公式化描述的无序线性表，设计一个C + +类来描述最大优先队列 (即利用程序3 - 1中的Linear List类） ，使得插入时间为( 1 )，对于n个元素的队列删除操作所需的最大时间为O (n)。2. 利用无序链表完成练习1（即利用程序3 - 8中的类C h a i n） 。3. 利用公式化描述的有序线性表重做练习 1，使得插入操作的时间为O (n)，删除操作的最大时间为( 1 )。4. 利用程序7 - 1中的类S h o r t e d C h a i n重做练习1。5. 给出抽象数据类型M i n P r i o r i t y Q u e u e的描述，并采用公式化描述的无序线性表，用 C + +类设计相应的最小优先队列。9.3 堆9.3.1 定义定义最大树（最小树） 每个节点的值都大于 （小于）或等于其子节点（如果有的话）值的树。最大树（max tree）与最小树（min tree）的例子分别如图9 - 1、9 - 2所示，虽然这些树都是二叉树，但最大树不必是二叉树，最大树或最小树节点的子节点个数可以大于 2。图9-1 最大树图9-2 最小树定义最大堆（最小堆） 最大（最小）的完全二叉树。图9-1b 所示的最大树并不是最大堆（max heap） ，另外两个最大树是最大堆。图9-2b 所示的最小树不是最小堆（min heap） ，而另外两个是。2 7 8第二部分数 据 结 构下载a) b) c) a) b) c) 由于堆是完全二叉树，利用 8 . 4节所介绍的公式化描述方案，可用一维数组有效地描述堆，利用二叉树的特性 4（见8 . 3节）可将堆中的节点移到它的父节点或它的一个子节点处。在后面的讨论中将用节点在数组中的位置来指定堆中的节点，如根的位置为1，其左孩子为2，右孩子为 3，等等。另外，注意到堆是完全二叉树，拥有n 个元素的堆其高度为 l o g2(n+ 1 ) ，因此，如果可在 O (h e i g h t) 时间内完成插入和删除操作，则这些操作的复杂性为O ( l o g2 n)。9.3.2 最大堆的插入图9-3a 给出了一个具有 5个元素的最大堆。由于堆是完全二叉树，当加入一个元素形成6元素堆时，其结构必如 9-3b 所示。如果插入元素的值为 1，则插入后该元素成为2的左孩子，相反，若新元素的值为 5，则该元素不能成为 2的左孩子（否则将改变最大树的特性） ，应把2下移为左孩子（如图 9 - 3 c所示） ，同时还得决定在最大堆中 5是否占据2原来的位置。由于父元素2 0大于等于新插入的元素 5，因此可以在原 2所在位置插入新的元素。假设新元素的值为2 1而不是5，这时，同图 9-3c 一样，把2下移为左孩子，由于 2 1比父元素值大，所以 2 1不能插入原来 2所在位置，因此把 2 0移到它的右孩子所在位置， 2 1插入堆的根节点（如图 9 - 3 d所示） 。图9-3 最大堆的插入插入策略从叶到根只有单一路径，每一层的工作需耗时( 1 )，因此实现此策略的时间复杂性为O(h e i g h t)=O ( l o g2 n)9.3.3 最大堆的删除从最大堆中删除一个元素时，该元素从堆的根部移出。例如，对图 9-3d 的最大堆进行删除操作即是移去元素2 1，因此最大堆只剩下五个元素。此时，图 9-3d 中的二叉树需要重新构造，以便仍然为完全二叉树。为此可以移动位置6中的元素，即2。这样就得到了正确的结构（如图9 - 4 a所示） ，但此时根节点为空且元素 2不在堆中，如果2直接插入根节点，得到的二叉树不是第9章优 先 队 列2 7 9下载a) c) d) b) 最大树，根节点的元素应为 2、根的左孩子、根的右孩子三者中的最大值。这个值是 2 0，它被移到根节点，因此在位置3形成一个空位，由于这个位置没有孩子节点， 2可以插入，最后形成的最大堆如图9-3a 所示。现在假设要删除2 0，在删除之后，堆的二叉树结构如图9-4b 所示，为得到这个结构，1 0从位置5移出，如果将1 0放在根节点，结果并不是最大堆。把根节点的两个孩子（ 1 5和2）中较大的一个移到根节点。假设将1 0插入位置2，结果仍不是最大堆。因此将1 4上移，1 0插入到位置4，最后结果如图9-4c 所示。图9-4 最大堆的删除删除策略产生了一条从堆的根节点到叶节点的单一路径，每层工作需耗时( 1 )，因此实现此策略的时间复杂性为O(h e i g h t)=O ( l o g2 n)9.3.4 最大堆的初始化在最大堆的几种应用中，包括 6 . 4 . 4节中工厂仿真问题的事件表，开始时堆中已经含有n (n0) 个元素。我们可以通过在初始为空的堆中执行 n 次插入操作来构建非空的堆，插入操作所需总时间为O(nl o gn)，也可利用不同的策略在(n) 时间内完成堆的初始化。假设开始数组a 中有n 个元素，另有n= 1 0，a 1 : 1 0 中元素的关键值为 2 0，1 2，3 5，1 5，1 0，8 0，3 0，1 7，2，1 ，这个数组可以用来表示如图 9-5a 所示的完全二叉树，这棵完全二叉树不是最大树。为了将图9-5a 的完全二叉树转化为最大堆，从第一个具有孩子的节点开始（即节点 1 0） ，这个元素在数组中的位置为 i = n/ 2 ，如果以这个元素为根的子树已是最大堆，则此时不需调整，否则必须调整子树使之成为堆。随后，继续检查以 i-1, i-2等节点为根的子树，直到检查到整个二叉树的根节点（其位置为1） 。下面对图 9 - 5 a中的二叉树完成这一系列工作。最初，i= 5