第 5 周：二项堆¶

二项堆其实并不是一个堆，而是一片堆森林——很多个堆。

设 \(B_x\) 是二项堆里面高度为 x 的堆。x = 0 的时候，这个堆只有一个结点；其他时候，\(B_k\) 的根节点有 k 个子树，分别是 \(B_0, B_1, \cdots, B_{k-1}\)。

\(B_k\) 有 \(2^k\) 个结点，它的深度为 \(d\) 的结点有 \(\binom{k}{d}\) 个。于是二项堆可以用它们表示任意大小的一整个堆。

二项堆的操作¶

最小值一定在所有堆的根之间。堆的数量是 \(O(\log n)\) 的，所以复杂度也是 \(O(\log n)\) 的。

就是和两个二进制数加起来一样的过程。两个 \(B_k\) 可以合成一个 \(B_{k+1}\)，相当于进位。

复杂度也是 \(O(\log n)\) 的。

给一个二进制数加一个 1，有 \(\frac{1}{2}\) 的概率进一次位，\(\frac{1}{4}\) 的概率进两次，\(\frac{1}{8}\) 的概率进三次……期望的操作数量是\(\sum_{i = 1}^{\infty} \frac{i}{2^i} = O(1)\)。

注意这也是个摊还复杂度，所以做可持久化会被卡。

比如要删除的最小值是 \(B_k\) 的根节点，那么删除之后会产生无主的 \(B_0, B_1, \cdots, B_{k-1}\)。把它们和原来的森林合并，复杂度是 \(O(\log n)\)。