前言: 二项堆复杂度分析是真的水。由于 DarkSharpness 实在是太懒了，所以图片全部来自 Wikipedia(所以要挂梯子).

先立个 Flag ，不用势能分析~~(才不是不会呢)~~

请不要用深色模式浏览本页，请点击右下角设置切换，否则图片会看不清

二项树

二项树如下递归定义:

$0$ 度的二项树只有 $1$ 个节点

$k(k \gt 0)$ 度的二项树包含 $1$ 个根节点，根节点下面有度数分别为 $k-1,k-2,\dots,0$ 的二项树，如图是一颗度数为 $0 ~ 3$ 的二项树:

(来自wikipedia)

不难发现，一颗度数为 $k (k \ge 0)$ 的二项树有恰好 $2^k$ 个节点。也不难发现，合并两颗度数为 $k (k\ge 0)$ 的二叉树，我们只需将其中一颗树连接到另外一棵树的根节点下面，便可以得到一颗度数为 $k + 1$ 的树，理论上一次 merge 只需要最坏 $O(1)$ 的时间。

二项堆

二项堆是基于二项树实现的，每颗树维护一个堆结构，节点之间的连接可以用链表实现。本文默认分析的是小根堆，大根堆同理。~~还是不会就爬。~~

*特别提示: 本文提到的常数指的是指复杂度表达式 f(n) 前面的系数，例如复杂度f(n) = O(n) 常数为 2 指的是

$\lim_{n\rightarrow\infty} \frac{f(n)}{n} = 2$

基本性质

对于一个二项堆，其存储了一些二项树，满足这些树的度数两两不相等，且每颗树及其子树满足堆结构，即节点是树中值最小的节点。

注意到一个度数为 $k$ 的二项树有恰好 $2^k$ 个节点，所以假设当前二项堆节点数量的二进制表示为 $\sum_{i=0}^n {a_i \cdot 2^i} (a_i = 0 \ or \ 1)$ (后文用 $\{ a_n \}$ 简记)，那么当前二项堆有一颗度数为 $i$ 的子树，当且仅当 $a_i = 1$ 。例如一个有 11 个节点的二项树，由于 11 的二进制表示为 $11 = (1011)_2$ ，那么这颗二项堆恰有度数为 $0,1,3$ 的三颗子树。

显然地，一个有 $n$ 个节点的二项堆，其含有的二项树的数量最多为 $\log_2(n) + 1$ 个，二项树的度数也不会超过 $\log_2(n)$.

合并两棵树

合并两棵树和之前提到的 merge 操作基本一致，不过需要特别注意，由于每颗树维护的是堆结构，因此我们需要把根节点值更大的树的根节点连接到根节点值更小的根节点下面，此时不难验证依然满足堆的性质。如下所示:

合并节点

显然地，该操作的最坏时间复杂度为 $O(1)$，常数取决于一次值比较所需的时间。

我们称之为 merge_tree 操作.

合并两个堆

合并两个堆的过程类似两个整数的加法过程:

假设两个堆节点数的二进制表示分别为 $\{a_n\},\{b_m\}$ (特别地，对于 $i \gt n$ ，$a_i$ 记为 0)，那么合并过程大致如下，类似正整数加法:

首先合并两个二项堆度数为 0 的二项树。如果当前只有 0 或 1 颗度数为 0 的二项树，那么保留当前的 0 或 1 颗树，不用合并。如果当前有 2 颗度数为 0 的二项树，那么合并为 1 颗度数为 1 的二项树。此时，我们认为，合并完了两个二项堆度数 $< 1$ 的二项树。

然后，假设已经合并完了两个二项堆度数 $ < k$ 的二项树，那么此时，最多会有 1(第一个堆) + 1(第二个堆) + 1(下面合并产生的) 颗度数为 $k$ 的二项树。类似地，当度数为 $k$ 的二项树总数为 0 或 1，那么什么都不做。如果总数为 2 或 3，那么随机合并其中两颗，合并出一颗度数为 $k + 1$ 的树。此时，合并完成了两个二项堆度数 $ < k + 1 $ 的二项树。

不难发现，只有当两个堆的节点数，在从低到高二进制加法中出现进位的时候，才会执行 merge_tree 操作。例如当一个节点数为 7 的树和一个节点数为 5 的树合并，我们首先写出两者的二进制表示 $7 = (111)_2 \ ,\ 5=(101)_2 $。因此其执行的合并操作如下:

首先合并两个堆的 2 个度数为 0 的两颗二项树，得到 1 个度数为 1 的二项树。再将其和第一个堆度数为 1 的二项树合并，得到一个度数为 2 的二项树。现在，我们得到了三颗度数为 2 的二项树，我们随机合并其中两颗，保留剩下那颗度数为 2 的二项树，得到一颗度数为 3 的二项树。最后，我们只有一颗度数未合并，而单独一颗无需处理。至此，操作结束，得到了 1 颗度数为 2 的二项树和一颗度数为 3 的二项树。再对比两个数字的二进制加法，最低位置 1 + 1 进位一个 1 ，留下的是 0 。第二位 1 + 0 + 1(进位) ，进位一个 1 ，留下一个 0 。第三位 1 + 1 + 1(进位)，进位一个 1 ，留下一个 1 。最后最高位保留一个 1，结束计算。

很直观地可以看出，合并的次数等于节点数二进制加法时进位次数，而这样的操作最多会执行 $\log_2(n + m)$ 次。

因此，该操作的最坏时间复杂度为 $O(\log(n + m))$，常数取决于一次值比较所需的时间。

我们称之为 merge_heap 操作。

查询最小值

为了便于复杂度证明以及后续展开，这里先分析查询最小值的时间复杂度。

查询最小值，一个朴素的办法就是将每颗树的值最小的节点 (即根节点) 两两比较，假设当前二项堆节点数为 $n$ ，那么最多比较次数不会超过 $\log_2 n$ ，即查询最坏复杂度为 $O(\log n)$ ，常数取决于一次值比较所需的时间。

这样的实现显然是不友好的。事实上，我们可以进行针对性优化，我们保留一个指向最小值的指针。

每次插入一个节点的时候，我们只需额外比较一次插入值和当前最小值的大小，指针指向更小的那一个即可。这会给插入一个节点带来 $O(1)$ 的额外开销，常数取决于一次值比较所需的时间。

每次删除一个最小值节点的时候，我们等删除结束后再用朴素方法维护得到最小值的指针即可。这会给删除一个节点带来 $O(\log n) $ 的额外开销，常数取决于一次值比较所需的时间。

此时，查询最小值只需访问一次指针即可，查询最坏复杂度为 $O(1)$ 。

我们称之为 top 操作。

删除最小值节点

由前面的查询最小值操作，我们多维护了一个指向最小值的指针，从而避免了查询最小值的高开销，将其部分均摊到了插入和删除操作上。

借助这个指向最小值的指针，我们可以按如下方法实现删除最小值节点:

最小值节点必然是一颗二项树的根节点，我们将这个二项树从二项堆中拿出来，得到一个由单独的二项树构成的二项堆，和原来的二项堆。假设原来的二项堆有 $n$ 个节点，我们新建的二项堆含有的是一颗度数为 $k (k \le log_2n)$ 的二项树。

此时，我们删除新生成的二项堆的根节点，由定义，断开该节点相连的边以后，我们会得到度数分别为 $k-1,k-2,…,0$ 的 k 颗二项树，将其记为最新的二项堆。此时，我们将最新的二项堆和旧的二项堆合并即可，即可以用 merge_heap 操作解决。

最后，别忘了还有更新最小值指针的 $O(\log n)$ 的额外开销。

因此，由前面的分析，我们容易知道，删除所需的最坏时间复杂度为 $O(\log (n + 2^k) ) + O(\log n) = O(\log n)$ ，常数取决于一次值比较所需的时间。

我们称之为 pop 操作。

插入一个节点

插入一个节点的过程简单来说如下:

将单节点作为仅含一个度数为 0 的二项树的二项堆。
合并当前堆和新生成的二项堆。

由前面对于合并堆的分析，我们不难看出，该操作所需的 merge_tree 操作次数取决于 $n$ 和 $1$ 做加法时候的进位次数，最坏时间复杂度为 $O(\log n)$ ，常数取决于一次值比较所需的时间。

但是若仅仅只有插入操作，那么假设一开始的节点数量为 $n$ ，进行了 $k$ 次连续的插入操作。分析单次加法操作，设 $x$ 和 $y$ 进行一次加法，$x$ 的二进制表示数位和 (后简称为数位和) 为 $s_x$ ，$y$ 的数位和为 $s_y$，若加法中进行了 $z$ 次进位，那么最后 $x + y$ 的数位和为 $s_x + s_y - z$ 。

因此从 $n$ 每次加一加到 $n + k$，设 $n$ 的数位和为 $s_1$，设 $n + k$ 的数位和为 $s_2$ ，而中间 $k$ 次加一，数位总和为 $k \times 1 = k$，因此进位次数为 $k + s_1 - s_2$ ，而易知，$s_1 \le \log_2 (n) + 1$ 。

因此，从节点数 $n$ 开始，连续插入 k 次的最坏时间复杂度为 $O(\log n + k)$ ，叠加上维护最小值的开销 $O(1)$，单次操作的平均最坏复杂度为

$O(\frac {\log {n}}{k} + 1) + O(1) = O(\frac {\log {n}}{k} + 1)$

当 $k$ 足够大，或者初始 $n$ 足够小，或者 $k$ 和 $\log n$ 同一个数量级，那么单次只需要均摊 $O(1)$ 次的 merge_tree 操作，单次复杂度可以降低到 $O(1)$ 。

因此，单次插入操作的均摊复杂度为 $O(1)$ ，常数取决于连续插入次数 $k$ 、初始节点数 $n$ 以及一次值比较所需的时间。

我们称之为 push 操作。

减小最小值

直接简化为一次删除 + 一次插入即可。易得最坏时间复杂度 $O(\log n)$，常数取决于一次值比较所需的时间。

我们称之为 decrease_key 操作。

其他操作

拷贝构造函数，可以通过遍历一遍节点，在 $O(m)$ 的时间内完成，其中 m 为被拷贝的二项堆的节点个数。。

析构函数，只需遍历一遍每个节点，在 $O(n)$ 的时间内完成，其中 n 为被拷贝的二项堆的节点个数。

拷贝赋值函数，可以通过先析构当前函数，再拷贝构造来实现。这样实现的时间复杂度为 $O(n + m)$ ，其中 n 为当前二项堆的节点个数，m 为被拷贝的二项堆的节点个数。

*如果实现了移动构造函数 (after C++ 11)，那么移动构造只需移走待移动对象的指针，所以时间复杂度为 $O(1)$ 。类似地，移动赋值函数只需在原地移动构造前先析构当前函数，因此其时间复杂度为 $O(n)$ (仅析构)。

就这?

就这? 你是啥fw? —— DarkSharpness

如果在 push 中，夹杂了一些 pop / decrease_key / merge_heap 操作 (显然穿插 top 是只读函数，不改变堆的结构，不会影响均摊复杂度)，那还能保证单次插入均摊时间复杂度为 $O(1)$ 吗? 当然可以，回到之前的定义，初始 $n$ 个节点，连续插入 k 次的最坏时间复杂度为 $O(\log n + k)$ 。

*后文 merge 若无特殊指明，指代 merge_heap

Decrease-key

对于穿插的一次 decrease_key 操作，其本质上也不会改变堆的元素数量，拥有某个度数的二项树的情况和操作之前完全一致 (例如原本 3 个节点，只有度数为 0 和 1 的二项树，drecrease_key，那么新的二项堆，也只有度数为 0 和 1 的二项树)。因此，对于 push 的均摊分析完全没有影响。

Pop-only

先不考虑 merge ，只考虑 pop。对于穿插的一次 pop 操作，设当前节点数为 $m$，若这次操作前面或之后存在一次 push 是节点数 $m - 1$ 增长到 $m$ ，我们可认为两次操作抵消掉，并且由于 push 单次最坏时间复杂度为 $O(\log n)$ ，我们可以把 push 的时间复杂度分摊到相抵消的 pop 上，pop 的最坏时间复杂度依然是 $O(\log n) + O(\log n) = O(\log n)$ ，但此时对应 push 的复杂度分摊给了 pop 降低为 O(1)。容易证明:

当 push 次数不超过 pop 的次数的时候，每次节点数从 $m - 1$ 上升为 $m$ 的 push 操作必然会对应一次节点数从 $m$ 下降的 $m - 1$ pop 操作。此时，每次 push 的复杂度都分摊给了 pop ，因此 pop 依然是最坏 $O(\log n)$ ，但是 push 降低为了均摊 $O(1)$。
当 push 次数超过 pop 的此时，每次节点数从 $m$ 下降的 $m - 1$ pop 操作必然会对应一次节点数从 $m - 1$ 上升为 $m$ 的 push 操作，假设节点数从 $n$ 上升到了 $n + t$，push 了 $k = t + d \ (d \ge 0)$ 次，即有 d 次抵消操作，那么所有 push 的最坏总复杂度为 $O(\log n + t) + d \times O(1) = O(\log n + k)$ ，类似之前 push 的分析，易得 pop 依然是最坏 $O(\log n)$ ，push 均摊 $O(1)$ 。

总之，混杂了 pop 以后，push 操作依然可以均摊 $O(1)$ ，不过是把部分复杂度摊给了 pop 罢了。

哪有什么岁月静好，不过是有人替你负重前行。

Merge-only

现在，我们只考虑 merge，不考虑 pop 操作。假设 merge 了 $m$ 次，push 了 $k$ 次，最后得到的堆的节点数为 $n$ 。那么，总操作的时间复杂度取决于 merge_tree 进行了多少次 (因此 merge_heap 和 push 的实现本质都是借助 merge_tree) 。因此，我们依然只需分析进位了多少次，假设 merge 的其他的二项堆的数位和 (前面说过了，默认二进制下的) 分别为 $s_1,s_2\dots s_m$ 的，堆的大小为 $x_1,x_2\dots x_m$，设初始节点数 $n_0$ 数位和为 $A$，最终节点数 $n$ 的数位和为 $B$ 。由此可知，进位数量最多为

$(\sum_{i = 1}^{m}{s_i}) + k + A - B。$

注意到 $s_i \le \log_2(x_i + 1)$，因此有

$\sum_{i = 1}^{m}{s_i} \le \log_2(\prod_{i = 1}^m{(x_i + 1)}) \le \log_2 \{ {(\frac{\sum_{i=1}^{m}(x_i + 1)}{m}) ^ m} \} \le m\log_2(1 + \frac n m)$

然后，发现这么搞做不出来…

你是fvv —— DarkSharpness

好吧，其实再认真看这一条:

$(\sum_{i = 1}^{m}{s_i}) + k + A - B。$

以及，$s_i \le \log_2(x_i + 1)$ …… 等一下! 每一次两个节点数为 $n_1$ 和 $n_2$ 的二项堆的合并操作要求地最坏复杂度为 $O(\log (n_1 + n_2)) $ 。因此对于每个 $s_i$ 次 merge_tree 的操作，我们可以将其直接分摊到 merge_heap 操作上。此时，不难发现，第 i 次合并的时间复杂度为 $\log_2(x_i + 1) \times O(1) \le O(\log (n_1 + n_2))$ ，没有破坏 merge 的性质，而分给 k 次 push 操作的总复杂度最坏为 $\log n_0 + k$，其中 $n_0$ 为初始节点数。因此，类似之前 push 的分析，我们可以得到 : push 操作依然是均摊 $O(1)$ 的时间复杂度。

哪有什么岁月静好，不过是另外还有一个人替你负重前行。

Pop + Merge

pop 和 merge 操作结合起来其实也差不多，借用前面单独分析情况的思想即可。我们只需要考虑依然只要考虑二进制下数位和的变化即可。假设连续 k 次插入操作，穿插了一些删除操作，和合并操作。假设删除前的数字为 $y_i$，那么删除后，数位最多减少 $\log_2 y_i$ 。而假设合并的数为 $s_i$，那么最多进位 $\log_2 s_i$ 次。类似地，设初始节点数数位和为 $A$，最终节点数的数位和为 $B$。那么最终进位次数不会超过

$\sum_i{\log_2 y_i}+ \sum_i{s_i} + k + A - B$

我们可以把每一项 $\log_2{y_i}$ 平摊到每次的 pop，而每一项 $s_i$ 平摊到 merge 操作上。借用前面的 pop-only 和 merge-only 的分析，我们不难得出，这不会破坏两者最坏 $O(\log n)$ 的性质。因此，此时，假设初始节点数为 n ，那么插入 k 次后，push 分到的最坏总复杂度为 $O(k + \log n)$ 。因此，借用前面的 push 的证明，我们可以得知，该情况下， push 操作的均摊复杂度为 $O(1)$ 。