堆和优先队列优先队列( 二 )

注意！在寻找节点的父节点、子节点的时候，乘法和除法都有因子d 。如果d是一个2的幂，则可以通过使用二进制的移位操作计算，这在计算机中是非常省时间的。但是如果d不是一个2的幂，则使用一般的乘除法计算，时间开销会急剧增加。有证据显示，实践中，堆可以胜过二叉堆
这些高级的数据结构很难使用一个数据结构来实现，所以一般都要用到链式数据结构，这种结构可能会使得其操作变慢。
零路径长（null path length）npl(X)：定义为从一个X节点到其不具有两个子节点的子节点的最短路径长，即具有0个或者1个子节点的节点npl=0，npl(null)=-1，任意节点的零路径长都比其各个子节点中零路径长最小值多1 。
左式堆（leftist heap）是指对于任意一个节点X，其左子节点的零路径长都大于等于其右子节点的零路径长。很显然，左式堆趋向于加深左路径。比如下边的两个堆，只有左边的是左式堆，堆的节点标示的是该节点的零路径长。
左式堆的实现中，需要有四个值：数据、左指针、右指针和零路径长。
定理：在右路径上有r个节点的左式堆必然至少有 2^r-1 个节点
merge 是左式堆的基本操作，insert 插入可以看成是一个单节点的堆与一个大堆的 merge ，deleteMin 删除最小值操作可以看成是首先返回、删除根节点，然后将根节点的左右子树进行 merge。所以 merge 是左式堆的基本操作。
假设现在有两个非空的左式堆H1和H2，merge操作递归地进行如下的步骤：
例如如下的两个堆：
将H2与H1的右子树（8--17--26）进行merge操作，此时（8--17--26）和H2的merge操作中又需要（8--17--26）和H2的右子堆（7--37--18）进行merge操作……如此递归得到如下的堆：
然后根据递归的最外层（回到H1和H2的merge的第二步），将上边合并的堆成为H1的右子堆
此时根节点（3）处出现了左右子堆不符合左式堆的情况，互换左右子堆并更新零路径长的值
斜堆（skew heap）是左式堆的自调节形式，实现起来极其简单。斜堆和左式堆的关系类似于伸展树和AVL树之间的关系。斜堆是具有堆序的二叉树，但是不存在对树的结构的现限制。不同于左式堆，关于任意结点的零路径长的任何信息都不保留。斜堆的右路径在任何时刻都可以任意长，因此，所有操作的最坏情形运行时间均为O(N) 。然而，正如伸展树一样，可以证明对任意M次连续操作，总的最坏情形运行时间是 O(MlogN) 。因此，斜堆每次操作的摊还开销（amortized cost）为O(logN)
斜堆的基本操作也是merge合并，和左式堆的合并相同，但是不需要对不满足左右子堆的左式堆条件的节点进行左右子堆的交换。斜堆的交换是无条件的，除右路径上所有节点的最大者不交换它的左右儿子外，都要进行这种交换。
比如将上述的H1和H2进行merge合并操作
首先进行第一步，除了交换左右子树的操作与左式堆不同，其他的操作都相同
将合并的堆作为H1的右子堆并交换左右子堆，得到合并后的斜堆
二项队列（binomial queue）支持merge、insert和deleteMin三种操作，并且每次操作的最坏情形运行时间为O(logN)，插入操作平均花费常数时间。
二项队列不是一棵堆序的树，而是堆序的树的集合，成为森林（forest）。堆序树中的每一棵都是有约束的二项树（binomial tree）。二项树是每一个高度上至多存在一棵二项树。高度为0的二项树是一棵单节点树，高度为k的二项树Bk通过将一棵二项树Bk-1附接到另一棵二项树Bk-1的根上而构成的。如下图的二项树B0、B1、B2、B3和B4 。
可以看到二项树Bk由一个带有儿子B0，B1，……，Bk-1的根组成。高度为k的二项树恰好有2^k个节点，而在深度d处的节点数为二项系数Cdk 。
我们可以使用二项树的集合唯一地表示任意大小的优先队列。以大小为13的队列为例，13的二进制表示为1101，从而我们可以使用二项树森林B3、B2、B0表示，即二进制表示的数中，第k位为1表示Bk树出现，第k位为0表示Bk树不出现。比如上述的堆H1和堆H2可以表示为如下的两个二项队列：
二项队列额merge合并操作非常简单，以上边的二项队列H1、H2为例。需要将其合并成一个大小为13的队列，即B3、B2、B0 。
首先H2中有一个B0，H1中没有，所以H2中的B0可以直接作为新的队列的B0的树
其次H1和H2中两个B1的树可以合并成一个新的B2的树，只需要将其中根节点较小的堆挂到根节点较大的堆的根节点上。这样就得到了三棵B2堆，将其中根节点最大的堆直接放到新队列中成为它的B2堆。

堆和优先队列 优先队列( 二 )

秒懂生活扩展阅读

堆和优先队列优先队列( 二 )