二项堆

二项树与表示不变量 ​

二项树 $B_0$ 是单节点；$B_k$ 由两棵 $B_{k-1}$ 连接而成，其中一棵根成为另一棵根的孩子。因此

$$|B_k|=2^k,height(B_k)=k,degree(root(B_k))=k.$$

最小二项堆是一组满足堆序的二项树：每个父键不大于孩子键，且每个度数 $k$ 至多出现一棵 $B_k$。根按度递增串成根表，并保存全局最小根指针或在需要时扫描根表。

若堆含 $n$ 个节点，出现哪些树阶正好对应 $n$ 的二进制展开，所以根数至多 $1+\lfloor {\log }_{2}n\rfloor$。唯一度数不变量是所有对数界的来源。

Link 与 Meld ​

link(T_1,T_2) 只接受两棵同阶树。比较两根，把较大根接为较小根的新孩子，得到高一阶的树；堆序与二项树形状同时保持，实际成本 $O(1)$。

meld(H_1,H_2) 先像归并有序链表一样按度合并两张根表，再从低度到高度扫描。遇两棵同阶树就 link 并向下一度进位；若连续出现三棵同阶树，须暂留一棵，把后两棵或前两棵中的一对连接，不能一次吞掉三棵。

根表最多覆盖 $O(\log (n_1+n_2))$ 个度数，故 meld 为最坏

$$O(\log (n_1+n_2)).$$

二进制加法真例 ​

大小 $5={101}_2$ 的堆含 $B_0,B_2$，大小 $3={011}_2$ 的堆含 $B_0,B_1$。合并时两棵 $B_0$ 连接成 $B_1$；它又与已有 $B_1$ 连接成 $B_2$；再与已有 $B_2$ 连接成 $B_3$。最终得到一棵 $B_3$，大小为 $8={1000}_2$。

每次连接都让较小键成为父节点，所以进位不会破坏堆序。若实现只按度连接却忘记比较根，树形仍像 $B_3$，但 find-min 已不再正确。

其他接口与复杂度 ​

若维护最小根指针，find-min 为最坏 $O(1)$；否则扫描 $O(\log n)$ 个根。插入可看作与 $B_0$ meld，最坏 $O(\log n)$。

delete-min 移除最小根 $r$。其孩子从度 $k-1$ 到 $0$ 排列，反转后成为合法递增根表，再与余堆 meld。扫描根、拆孩子与合并都只涉及 $O(\log n)$ 个树阶，故最坏 $O(\log n)$。

decrease-key 沿父链上浮，最坏走树高 $O(\log n)$。若通过交换键和载荷实现，外部句柄可能随载荷移动；若句柄必须稳定定位逻辑对象，就要交换完整对象身份或执行节点切接并重新证明不变量。

与相邻堆的区分 ​

二叉堆公理库二叉堆Binary heap以近完全二叉树表示并满足父子堆序的优先队列结构。用一棵完全二叉树换取连续数组局部性，但普通 meld 为线性。二项堆用多棵树和二进制进位把 meld 降到最坏对数。

Fibonacci Heap公理库Fibonacci 堆Fibonacci heap以延迟合并和级联切断取得常数摊还插入、合并与减键的可并优先队列。保留类似的按度 consolidation，却把它延迟到 delete-min，从而令 insert、meld、decrease-key 达到摊还常数。二项堆没有级联切断，不能借用这张成本表；它的优势是结构和最坏界更直接。

失败边界 ​

根表若允许同阶树长期并存，根数可能线性，最小根扫描和下一次合并都会退化。删除最小根后若不反转孩子顺序，按度归并逻辑也会错误。

重复键不影响堆序，但必须用节点身份区分句柄。Meld 后两堆的旧根表对象应视为已被消费；若调用方继续修改旧堆头，会让同一节点同时属于两份结构。

参考资料

• Jean Vuillemin, “A Data Structure for Manipulating Priority Queues,” Communications of the ACM 21(4), 1978.
• Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., MIT Press, 2022, Chapter 19.
• Robert E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983.