可合并堆简介

有时候我们面临着合并两个堆的需求，举个栗子：

某市有俩医院，分别用一个优先级队列记录病人就医顺序，但是突然一家医院设施全部瘫痪所以病人需要迁移到另一所医院就医，那么该怎样将这个两个优先级队列合并成一个新的优先级队列呢？ 另外有些图算法也依赖优先级队列的合并。

假设我们原先用普通的二叉堆来实现优先级队列，那么并没有比较好的合并二者的方法，只有简单的merge两个数列然后重新调用buildHeap函数(参加二叉堆),这个时间复杂度为O(n)。看起来并不算太差，但我们希望更好。

我们定义可支持高效合并的堆为可合并堆（meldable heap），显然普通的二叉堆并不是可合并堆。我们怎样构造一种可合并堆呢？

The Intuition

合并堆的过程和数值加法有神似。

二进制加法复杂度为O(max{log(a),log(b)}),如果我们能类比二进制加法来定制一个堆，那么合并复杂度就是log(n)级别的！

类比

我们将堆表示为多个元素个数为2的自然数幂的“packet” ，每个packet对应二进制中的某一位。那么将堆合并就可以看做每个对应位的“packet”结合、进位！

packet

为了支持可合并堆，我们对packet有以下要求：

1.包含元素的个数必须为2的自然数幂

2.要能以O(1)的时间复杂度高度合并两个相同大小的packet

3.要能以O(1)的时间找到每个packet的最值

4.能高效拆分成含有1，1，2，4，…，2^(n-1)个元素的子 packet（删除元素要用！）

对于上述要求，显然二项树（之前文章有写过，可以关注查看一下）可以完美实现需求！

二项堆(Binominal Heap)

由一组堆序二项树按照 size 大小单调排列的、并且每种 size 的二项树至多只有一个，构成的数据结构称为二项堆(Binominal Heap)。其属性用一个vector在相应位置存储各个二项树即可。

1.合并——meldWith()

这个是二项堆的核心方法，几乎所有的其它操作都依赖这个方法来实现。其操作过程和链表实现二进制加法很类似，具体要点简介如下：

1.我们需要创建一个用于保存融合“进位”的 packet——bonus

2.需要对“求和结果”进行“补位”操作，因为结果“位数”必定不小于加数“位数”

3.逐位进行融合，首先不考虑进位进行部分融合，得到的结果会有三种情况：

(1) 融合后 packet 的 size=0，那么结果中本位必定和之前的进位 packet 一致，而下一位的进位 bonus 为空 packet。

(2) 融合后 packet 的 size 和本位理论 size 一样大，这时就要看 bonus 的情况了。继续融合，得到两种子情形：

<2.1> 完整融合后 packet 的 size 和本位理论 size 一样大，此时结果中的本位即为完全融合的 packet，而进位 bonus 为空。

<2.2> 完整融合后 packet 的 size 是本位理论 size 两倍大，此时结果中的进位 bonus 为完全融合的 packet，而结果中本位为空。

(3) 融合后 packet 的 size 是本位理论 size 两倍大，这时结果中的本位可以确定为之前进位的 packet，而下一位的进位 bonus 可以赋值为部分融合的结果。

4.此时检查进位，若不为空，则用进位 packet 和二项堆继续进行融合，此时和上述3.2过程很类似，但要注意此时可能存在最高位进位的特殊情形，需要单独处理。

详细代码如下所示（代码略长所以图有些小，可以点开放大看）：

2.添加新元素——push()

可以看做原有二项堆和一个只有单个元素的二项堆的合并，时间复杂度O(log(n))。

3.查找最小元素——top()

遍历所有子二项树，查找最小值，耗时O(1)*O(log(n))=O(log(n))。注意只有 size>0 的二项树中保存的 key 才真正有意义。

4.删除最小元素——pop()

含有最小元素的那个packet去掉一个元素后就不满足大小为2的自然数幂了额。不过一个有趣的事实是：

所以我们可以将删掉元素的那个 packet 拆分为 n 个子 packet 构成的二项堆（这就是为什么要求 packet 支持高效拆分的理由），然后进行两个堆的合并即可。其时间复杂度为O(1+log(n))=)(log(n))。

完整序列操作演示

一段完整的二项树添加元素、合并、删除元素过程如下所示：

摊还分析

1.若只push元素，那么平均复杂度为O(1)，这说明从0构建一个有n个元素二项堆时间复杂度为O(n)，而从0逐项构建二叉堆时间复杂度为O(nlog(n))!

2.当有删除操作时，摊还分析复杂度并不成立。因为处于边界情形时交替进行插入、删除操作会持续导致O(log(n))的操作，进行k次则整体复杂度恶化为O(klog(n)) 。

总结与展望

本文主要介绍了一种可合并堆——二项堆。首先将其和二进制加法进行了类比，然后引出其基本实现元素——packet(二项树)，并利用 packet 构成二项堆。然后本文大致介绍了其代码实现，同时指出了其在面临边界特殊情形时操作时间复杂度变差的理由。

为了规避边界操作这一风险，我们后面将介绍 lazy 二项堆。

同时二项堆仍没有解决堆的decrease key难题，后面将介绍斐波那契堆来高效改变key值。

如果觉得这种可合并堆实现比较复杂，那么后面介绍的左倾堆实现起来就很简单啦。

Acknowledgement

本文大部分动图都来自Keith Schwarz @ Stanford，向其表示感谢！