Lazy Binomial Heaps

motivation

为什么我们需要Binomial heaps(二项堆)？ Binary heaps(二叉堆) 实现的优先队列就已经有了 O(logn) 复杂度的 enqueue(insert) 和 extractMin(deleteMin)，findMin O(1), 实际运作过程中就已经很快了，为何还需要其他堆呢？

因为很多图算法都不止依赖于优先队列的这两种操作，还依赖于它提供的额外操作: meld (merge or union)——合并两个优先队列 (MSTs via Cheriton-Tarjan) ，decreaseKey——提高队列内某个元素的priority (Shortest paths via Dijkstra)，add_to_all——add $\Delta$ k to the keys of each element in pq.

Meldable Priority Queue

试想如何用二叉堆实现的优先队列实现两个 pq 的合并呢？可以两个混在一块 heapify，O(n) 看起来还可以；或是调用接口 A.insert(B.deleteMin())，O(nlogn) 看起来就不太行。

因为二叉堆是完全二叉树，所以很难简单地把两个二叉堆通过 link 合并成新的二叉堆。

how to meld

而如果我们用二进制来表示这两个 pq，那么合并相当于二进制加法，这样复杂度就变成了 O(logn+logm)。在这种思路下，我们把 n 和 m 表示成两个 packets collection每一个 packet 2 的幂次大小，用来存数。然后用指针把这些 packet 和 node link，这样合并就变成了：

intuition

meld

lazy binomial heap

where we stand

在继续下面的内容之前我们先看一下 eager binomial heap 的性能表现。

performance of eager binomia heap

(MINIMUM 因为存了指针，在 insert 和 extractMin 时顺便 update，所以 $\Theta(1)$ .）

根据“对于 comparison-based sort 需要 $\Omega(n\log n)$ ”这个定理，看看我们现在的处境可以发现，能优化的地方不多。我们不可能让 insert 和 extractMin 都优化到更快——指都小于O(logn)，但是却可以考虑使其中一项操作变得更快。

那么就考虑优化 insert 吧！看看能不能使在 worst-case 也可以 $O(1)$ ，毕竟删前总要插。那么因为 insert 或 enqueue 是用 meld 实现的，那么 meld 也必须 $O(1)$ 了。

问题：为什么我们在插入时就要维护呢，我们都不一定要对新插入进来的节点做任何操作？

思路：我们索性 insert 或 meld 的时候就只维护 min 指针，然后直接把 H₂ 直接连进来，复杂度 $O(1)$ ，然后如果有其他要维护的事情就全交给 extractMin 吧！

例：对于 lazy binomial heap 插入 4, 7, 3, 6, 5. (In practice，实现是双向循环链表)

lazy meld

试想一下这样实现 lazy meld 之后，extractMin 会怎样？

先 remove min 指针所指向 binomial tree 的 root，把 B_k 分裂成 B_K-1...B₀ 再 lazy meld 回来
再 update min 指针

可达鸭眉头一皱，发现在最后 update 时的复杂度取决于此时 heap 里面 tree 的个数，O(t)。而t = O(n)，于是 extractMin O(n)。

像极了中学假期在家的你。白天父母外出工作，于是玩的时候不需要考虑收拾可以随意地造。其余的事情就等着之后掐着父母下班的点再把一切收拾干净，装作这一天平静度过什么都没有发生一样。恭喜你年纪轻轻就已经是个优化带师，成功地把 van 的复杂度降到了最低。

接着来解决 extractMin 变 O(n) 的问题。分析可知这是由于我们不再限制 B_k 的order唯一，meld 时只单纯 link。那么就考虑我们对应 lazy meld，在 extractMin 时把该合并的合并了，保证 order 唯一这样我们的树的个数就变 O(log n)。

这个在 extractMin 时重新合并 tree 使 order 再次唯一的操作在某些教材上称之为 coalesce step.

coalesce step

简言之， coalesce step 就是在extractMin之后，update min 指针之前合并所有order相同的 tree 使 order 唯一。

考虑到同 order 合并，且 order 破碎，使用基排序来高效合并。

coalesce step

先创建 O(logn)个箱子，O(logn)。再 distribute 按 order 所有的 tree，O(t)。再合并所有需要合并的 tree，O(t)。总复杂度 O(t+logn)。

所以此时 extractMin 的实现:

先 remove min 指针所指向 binomial tree 的 root，把 B_k 分裂成 B_K-1...B₀ 再 lazy meld 回来, O(logn)
再 coalesce step, O(t+logn)
最后 update min 指针, O(logn)

很遗憾，extractMin worst-case 复杂度 O(t+logn) = O(n)。heap 里全是 B₀. 而 insert, meld, minimum O(1). 即便我们此时还不考虑 decreaseKey，但依旧是O(logn)，取决于树的高度。

extractMin

The story so far

lazy binomial heap 的 worst-case 性能似乎看起来并不乐观。实际上我们是以牺牲了extractMin 的性能为代价换取了 meld 的高效。那么这个数据结构的均摊复杂度如何呢？

继续使用上次扩充的 potential method.

首先 meld 和 insert worst-case $\Theta(1)$ , amortized 同样 $\Theta(1)$ 。

Minimum 存了指针，所以依旧 $\Theta(1)$ 。

最后是关于extractMin的 amortized analysis. 依旧令 $\Phi(S)$ 表示当前 heap 里 tree 的数量。假设 extractMin 前 $\Phi(S_{before}) = t$ 。
actual cost of step 1 $= O(\log n)$
actual cost of step 2 $= O(t+\log n)$
actual cost of step 3 $= O(\log n)$ （前面都提到过）
$\Phi(S_{after}) = \log n$

$\Delta\Phi = -t + \log n$ , actual cost $= O(t+\log n)$ .
因此“均摊”复杂度 = $O(t+\log n) + C\cdot (-t+\log n) = O(\log n)$

最终 lazy binomial heap 的性能如下：

performance of lazy binomial heap

（两个性能的图均来自 Stony Brook CSE-548 lecture9）

后记

主要参考了大S的 cs-166，Stony Brook的 CSE-548。

前者会讲很多思路，好像旨在告诉你提出解决办法的人是他们如何思考这个问题的，把你带入到情境中。但是有时候会显得很冗长，啰嗦。而实际上虽然内容很长，200+的slides，但其实并没有披露特别多的细节。而且因为屏蔽了一些细节，所以在一些时候分析的时候就会跟屏蔽细节的结论相悖。

后者很扎实、很干。上来就硬货怼脸的感觉，而且会涉及到比较多的细节，很详尽。可能因为是CSE的缘故...总之如果抱着致知的态度，刨根问底一探究竟的话，极为推荐。可能大S的人都是那种知道顶层思路，享受自己回去自己研究实现的乐趣。确实本来就没有一个正确答案，只要思路对，能实现，细节自己慢慢扣是极好的。

啊...如果本着膜一下名校，去看下CMU的课件，我觉得还是算了吧。看了也白看，内容很少，看了也白看，而且写到 3. Binomial heaps 后面就跟了一句话，To be finished. 在后面就是下一个 lecture的另外的内容了...

最后记一下这些 slides 中的小错。cs-166: performance score find_min $\Theta(1)$ ，而在分析时采用的是不维护 min 指针而是去find_min O(t)，感觉没得洗。另外就是太长了...不利于阅读...CSE-548 对于lazy binomial heap 是否维护 min 指针的描述前后矛盾。维护顺带的事儿，不维护的话，O(t)啊！？另外可能会不一致在一些操作的先后顺序是先合并还是先remove没有影响。

不维护

使用

create

Lazy Binomial Heaps

motivation

Meldable Priority Queue

更多细节——Recap from last time

lazy binomial heap

where we stand

coalesce step

The story so far

后记