二项队列/二项堆

定义

二项树

定义

二项堆是由二项树组成的，所以我们需要先了解二项树。
我们递归地定义二项树
- 二项树Bk是一个带阶数k地有序树
- B0是一个只包含一个根节点地树（阶数为0）
- Bk是由两颗B~~k-1~~连接而成的。连接时，一棵树的根成为另一棵树根的最左边的子节点
以下是示意图

graph TD; subgraph B_0 A(("Node")); end

graph TD; subgraph B_1 A(("Root")); B(("Child")); A-->B; end

graph TD; subgraph B_2 A(("Root")); B(("Child of Root")); C(("Grandchild")); D(("Child of Root")); A-->B; A-->D; B-->C; end

graph TD; subgraph B_3 A(("Root")); B(("Child")); C(("Child")); D(("Child")); E(("Grandchild")); F(("Grandchild")); G(("Grandchild")); H(("Great-Grandchild")); A --> B; A --> C; A --> D; B --> E; B --> F; C --> G; E --> H; end

性质

二项树有如下重要性质：
- 节点数：Bk有2^k^个节点
- 高度：B_k_的高度为k
- 根的度数：Bk的根有k个子节点，这k个子节点分别是B~~k-1~~，B~~k-2~~，…, B0的根
- 组合数关系：在深度d处，恰好有C(k, d)个节点，数值上等于多项式中对应地多项式系数，这也是二项树这个名字的来源。

二项堆

现在可以定义二项堆了，二项堆就是一个满足以下两个条件的二项树集合：
- 堆序性质：堆中每棵二项树都满足最小堆性质
- 唯一阶数性质：对于任意阶数k，二项堆中最多仅包含一棵Bk树

结构

二项堆与二进制有着紧密联系。对于一个有n个节点的二项堆，它的结构由n的二进制表达唯一确定。
- 如果n的二进制表达中第i位为1，那么这个堆中包含一棵Bi树
- 如果n的二进制表达中第i位为0，那么这个堆中不包含Bi树
例：对于一个包含13个节点的二项堆，由于13的二进制表达位1101，该堆包含B0, B2, B3
在实现上，二项堆一帮由一个跟链表来表示，这个链表将堆中所有二项树的根连接起来，通常按照阶数递增排序

操作

与自平衡堆类似，二项堆的核心操作是归并

归并

二项堆的归并操作与二进制加法高度相似
按照以下逻辑进行：
- 1 + 0 = 0
  - 如果一个二项堆有Bk，而另一个没有，且没有进位，直接将Bk作为归并后的Bk
- 1 + 1 = 10
  - 如果两个二项堆都有Bk，没有进位，（或一个为空但有进位）那么归并后的二项堆无Bk，两个Bk组合成B~~k+1~~作为进位
- 1 + 1 + 1 = 11
  - 如果两个二项堆都有bk，且有进位，那么归并后的二项堆有Bk，且有进位B~~k+1~~