文章目录
  1. 二项队列
  2. 合并
  3. 删除
  4. 具体实现

二项队列

二项队列是堆序树的集合，这些堆序树是是二项树，每一个高度上最多存在一个二项树；高度为0的二项树是一个单节点树，高度为k的二项树$B_{k}$通过将一个$B_{k-1}$二项树附接到另一个$B_{k-1}$二项树上；如下图示所示，高度为0、1、2、3、4的二项树如下。

 

高度为k的二项树的节点数为$2^{k}$，因此二项队列可以有任意个节点。

合并

对两个二项队列，首先取并集，按树的高度由高到低考察，对于高度相同的，将其中一个附接到另外一个的根节点上，此时可能又会与已有的二项树高度相同，那么再次合并；遍历一遍之后合并操作完成。

同样的，插入就是合并的特殊情形。

删除

一般指删除最小的根节点。首先，从二项队列中删除这个根节点所在的树，然后这个树删除根节点变成含有两个二项树的二项队列，然后与之前的二项队列合并。

具体实现

使用链表，每个节点指向自己的第一个子节点与右兄弟节点，对于根节点，则是指向下一个二项树的根节点(二项树按照高度排序)。