6. 1 模型
优先队列是允许至少下列两种操作的数据结构： insert(插入），它的作用是显而易见的；以及deleteMin(删除最小者）， 它的工作是找出、返回并删除优先队列中最小的元素。insert操作等价于enqueue(入队），而deleteMin则是队列运算dequeue(出队）在优先队列中的等价操作。
如同大多数数据结构那样，有时可能要添加一些其他的操作，但这些添加的操作属于扩展的操作，而不是图6-1所描述的基本模型的一部分。
6.2 一些简单的实现
有几种明显的方法可用于实现优先队列。我们可以使用一个简单链表在表头以0(1)执行插入操作，并遍历该链表以删除最小元，这又需要O(N)时间。另一种方法是始终让链表保持排序状态；这使得插入代价高昂(O(N)) 而deleteMin花费低廉(0(1))。基于deleteMin的操作从不多于插入操作的事实，前者恐怕是更好的想法。
另一种实现优先队列的方法是使用二叉查找树，它对这两种操作的平均运行时间都是O(log N)。尽管插入是随机的，而删除则不是，但这个结论还是成立的。记住我们删除的唯一元素是最小元。 反复除去左子树中的节点似乎会损害树的平衡，使得右子树加重。 然而，右子树是随机的。 在最坏的情形下，即deleteMin将左子树删空的情形下，右子树拥有的元素最多也就是它应具有的两倍。 这只是在期望的深度上加了 个小常数。 注意，通过使用 棵平衡树，可以把这个界变成最坏情形的界；这将防止出现坏的插入序列。
使用查找树可能有些过分，因为它支持许许多多并不需要的操作。 我们将要使用的基本的数据结构不需要链，它以最坏情形时间0(logN)支持上述两种操作。 插入操作实际上将花费常数平均时间，若尤删除操作的干扰，该结构的实现将以线性时间建立 个具有N项的优先队列。
6.3二叉堆
我们将要使用的这种工具叫作二叉堆(binary heap) , 它的使用对于优先队列的实现相当普遍，以至于当堆(heap)这个词不加修饰地用在优先队列的上下文中时，一般都是指数据结构的这种实现。在本节，我们把二叉堆只叫作堆。像二叉查找树一样，堆也有两个性质，即结构性和堆序性。恰似AVL树，对堆的一次操作可能破坏这两个性质中的一个，因此，堆的操作必须到堆的所有性质都被满足时才能终止。事实上这并不难做到。
6.3. 1 结构性质
堆是一棵被完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树(complete binarytree)。图6-2给出了一个例子。
完全二叉树的高是 log N，显然它是0(logN)。
一个重要的观察发现，因为完全二叉树这么有规律，所以它可以用一个数组表示而不需要使用链。
对于数组中任一位置i上的元素，其左儿子在位置2i上，右儿子在左儿子后的单元(2i +1)中，它的父亲则在位置[i/2]上。因此，这里不仅不需要链，而且遍历该树所需要的操作极简单，在大部分计算机上运行很可能非常快。这种实现方法的唯一问题在于，最大的堆大小需要事先估计，但一般这并不成问题（而且如果需要， 我们可以重新调整大小）。在图6-3中，堆大小的限界是13个元素。该数组有一个位置0, 后面将详细叙述。
因此， 一个堆结构将由一个(Comparable对象的）数组和一个代表当前堆的大小的整数组成。图6-4显示一个优先队列的架构。
本章我们将始终把堆画成树，这意味着具体的实现将使用简单的数组。
6.3.2 堆序性质
让操作快速执行的性质是堆序性质(heap-order property)。由于我们想要快速找出最小元，因此最小元应该在根上。如果我们考虑任意子树也应该是一个堆，那么任意节点就应该小于他的所有后裔。
应用这个逻辑，我们得到堆序性质。在一个堆中，对于每一个节点X,X 的父亲中的关键字小于（或等于）X 中的关键字，根节点除外（它没有父亲）。
https://gitee.com/sunyunjie/DataStrycturesAndAlgorithmAnalysis
6.3.3 基本的堆操作
insert（插入）
为将一个元素X插入到堆中，我们在下一个可用位置创建一个空穴，否则该堆将不是完全树。如果X可以放在该空穴中而并不破坏堆的序，那么插入完成。 否则，我们把空穴的父节点上的元 素移入该空穴中，这样，空穴就朝着根的方向上冒一步。 继续该过程直到X能被放入空穴中为止。如图6-6所示，为了插入14, 我们在堆的下一个可用位置建立一个空穴。 由于将14插入空穴破坏了堆序性质，因此将31移入该空穴。在图6-7中继续这种策略，直到找出置入14的正确位置。
如果欲插入的元素是新的最小元从而一直上滤到根处，那么这种插入的时间将长达O(logN)。 平均看来，上滤终止得要早；
deleteMin(删除最小元）
deleteMin以类似于插入的方式处理。找出最小元是容易的，困难之处是删除它。当删除一个最小元时，要在根节点建立一个空穴。由于现在堆少了一个元素，因此堆中最后一个元素X 必须移动到该堆的某个地方。如果X可以被放到空穴中，那么dele七eMin完成。不过这一般不太可能，因此我们将空穴的两个儿子中较小者移入空穴，这样就把空穴向下推了一层。重复该步骤直到X可以被放入空穴中。因此，我们的做法是将X置入沿着从根开始包含最小儿子的一条路径上的一个正确的位置。
图6-9中左图显示了deleteMin之前的堆。删除13后，我们必须试图正确地将31放到堆中。31 不能放在空穴中，因为这将破坏堆序性质。于是，我们把较小的儿子14置入空穴，同时空穴下滑一层（见图6-10)。重复该过程，山于31大于19, 因此把19置入空穴，在更下一层上建立一个新的空穴。然后，由于31还是太大， 因此再把26置入空穴，在底层又建立一个新的空穴。最后， 我们得以将31置入空穴中（图6-11)。这种一般的策略叫作下滤(percolate down)。在其实现例程中我们使用类似于在insert例程中用过的技巧来避免进行交换操作。
这种操作最坏情形运行时间为 O(log N)。平均而言，被放到根处的元素几乎下滤到堆的底层（即它所来自的那层），因此平均运行时间为 O(log N) 。
6. 5 d-堆
二叉堆是如此简单，以至于它们几乎总是用在需要优先队列的时候。d-堆是二叉堆的简单推广，它就像一个二叉堆，只是所有的节点都有d个儿子（因此，二叉堆是2-堆）。
图 6-19 表示的是一个 3-堆。注意，d-堆要比二叉堆浅得多，它将 insert操作的运行时间 改进为 O(logd N)。然而，对于大的 d, deleteMin 操作费时得多，因为虽然树是浅了，但是 d个儿子中的最小者是必须要找出的，如使用标准的算法，这会花费d-1次比较，于是将操作的用时提高到 O(d logd N)。如果 d 是常数，那么当然两个的运行时间都是 O(log N)。虽然仍然可以使用一个数组，但是，现在找出儿子和父亲的乘法和除法都有个因子 d, 除非 d 是 2 的幕，否则将会大大增加运行时间，因为我们不能再通过移一个二进制位来实现除法了。d-堆在理论上很有趣，因为存在许多算法，其插入次数比 dele匡Min 的次数多得多（因此理论上的加速是可能的）。当优先队列太大而不能完全装入主存的时候，d-堆也是很有用的。在这种情况下，d-堆 能够以与B树大致相同的方式发挥作用。最后，有证据显示，在实践中4-堆可以胜过二叉堆。
6.6 左式堆
设计一种堆结构像二叉堆那样有效地支持合并操作（即以o(N)时间处理一个merge)而且 只使用一个数组似乎很困难。 原因在于，合并似乎需要把一个数组拷贝到另一个数组中去，对于相同大小的堆这将花费时间O(N)。 正因为如此，所有支持有效合并的高级数据结构都需要使用链式数据结构。
6. 6. 1 左式堆性质
我们把任一节点X的零路径长(null pathleng th) npl (X)定义为从X到一个不具有两个儿子的节点的最短路径的长。因此，具有0个或一个儿子的节点的npl 为o, 而npl(null)= -1。在图6-20的树中， 零路径长标记在树的节点内。
注意，任一节点的零路径长比它的各个儿子节点的零路径长的最小值大l。这个结论也适用少于两个儿子的节点，因为null的零路径长是-1。
左式堆性质是：对于堆中的每一个节点X, 左儿子的零路径长至少与右儿子的零路径长相等。图6-20中只有一棵树，即左边的那棵树满足该性质。这个性质实际上超出了它确保树不平衡的要求，因为它显然偏重于使树向左增加深度。确实有可能存在由左节点形成的长路径构成的树（而且实际上更便于合并操作） 因此，我们就有了名称左式堆(leftist heap)。
因为左式堆趋向于加深左路径，所以右路径应该短。事实上，沿左式堆右侧的右路径确实是该堆中最短的路径。否则，就会存在过某个节点X的一条路径通过它的左儿子，此时X 就破坏了左式堆的性质。
定理6.2 在右路径上有r个节点的左式树必然至少有2^r-1个节点。
6.6.2 左式堆操作
对左式堆的基本操作是合并。 注意，插入只是合并的特殊情形，因为我们可以把插入看成 是单节点堆与一个大的堆的merge。 首先，我们给出一个简单的递归解法，然后介绍如何能够非递归地执行该解法。 我们的输入是两个左式堆H1和H2, 见图6-21。 读者应该验证，这些堆确实是左式堆。 注意， (最小的元素在根处。 除数据、左引用和右引用所用空间外，每个节点还要有一个指示零路径长的项。
如果这两个堆中有 个堆是空的，那么我们可以返回另外一个堆。 否则，合并这两个堆， 比较它们的根。 首先，我们递归地将具有大的根值的堆与具有小的根值的堆的右子堆合并,, 在本例中，我们递归地将H2与h1的根在8处的右子堆合并， (18得到图6-22中的堆。
由于这棵树是递归形成的，而我们尚未 对算法描述完毕，因此，现在还不能说明该是如何得到的。 不过，有理由假设，最后 的结果是一个左式堆，因为它是通过递归的步骤得到的。 这很像归纳法证明中的归纳 图6-22 将H2 与凡的右子堆合并的结果假设。 既然我们能够处理基准情形（发生在一棵树是空的时候），当然可以假设，只要能够完成合并那么递归步骤就是成立的,这是递归
6.7 斜堆
斜堆(skew heap)是左式堆的自调节形式，实现起来极其简单。 斜堆和左式堆间的关系类似于伸展树和AVL树间的关系。 斜堆是具有堆序的二叉树，但不存在对树的结构限制。 不同于左 式堆，关于任意节点的零路径长的任何信息都不再保留。 斜堆的右路径在任何时刻都可以任意长，因此，所有操作的最坏情形运行时间均为O(N)。 然而，正如伸展树一样，可以证明（见第11章）对任意M次连续操作，总的最坏情形运行时间是O(Mlog N)。 因此，斜堆每次操作的摊还开销 (amortized cost) 为 O(logN)。
与左式堆相同，斜堆的基本操作也是合并操作。merge例程还是递归的，我们执行与以前完全相同的操作，但有一个例外，即：对于左式堆，我们查看是否左儿子和右儿子满足左式堆结构性质， 并在不满足该性质时将它们交换。但对于斜堆，交换是无条件的，除那些右路径上所有节点的最大者不交换它的左右儿子的例外外， 我们都要进行这种父换。这个例外就是在自然递归实现时所发生的情况，因此它实际上根本不是特殊情形。此外，证明时间界也是不必要的，但是，由于这样的节点肯定没有右儿子，因此执行交换是不明智的（在我们的例子中，该节点没有儿子，因此我们不必为此担心）。另外，仍设我们的输入是与前面相同的两个堆，见图6-31如果我们递归地将H2与H1
的根在8处的子堆合并，那么将得到图6-32中的堆。
注意，因为右路径可能很长，所以递归实现可能由于缺乏栈空间而失败，尽管在其他方面性能是可接受的。 斜堆有一个优点，即不需要附加的空间保留路径长以及不需要测试以确定何时交换儿子。 精确确定左式堆和斜堆的右路径长的期望值是一 个尚未解决的问题（后者无疑更为困难）。 这样的比较将更容易确定平衡信息的轻微遗失是否可由缺乏测试来补偿。
6.8 二项队列
虽然左式堆和斜堆都在每次操作以O(logN)时间有效地支持合并、插入和deleteMin,但还是有改进的余地，因为我们知道，二叉堆以每次操作花费常数平均时间支持插入。二项队列支持所有这三种操作，每次操作的最坏情形运行时间为0(logN) , 而插入操作平均花费常数时间。
6. 8. 1 二项队列结构
二项队列(binomial queue)与我们已经看到的所有优先队列的实现的区别在于，一个二项队 列不是一棵堆序的树，而是堆序的树的集合，称为森林(forest)。每一棵堆序树都是 有约束的形式，叫作二项树(binomial tree , 后面将看到该名称的由来是显然的）。每一个高度上至多存在一棵二项树。高度为0的二项树是一棵单节点树；高度为k的二项树凡通过将一棵二项树 Bk -I附接到 另 一棵二项树 Bk-I的根上而构成。图6-34显示二项树 B0,B1,B2,B3以及B4.
从图中看到，二项树队由一个带有儿子B0, B1，。。。，BK-1的根组成。高度为k的二项树恰好有2k个节点，而在深度d 处的节点数是二项系数(d)。如果我们把堆序施加到二项树上并允许任意高度上最多一棵二项树，那么就能够用二项树的集合表示任意大小的优先队列。例如，大小为13 的优先队列可以用森林B3, B2, B。表示。我们可以把这种表示写成1101, 它不仅以二进制表示了13'而且也表示这样的事实：在上述表示中，B3, B2, B。出现，而B1则没有。
网友评论