二项堆

二项堆(Binomial Heap)是一种类似于二叉堆的堆结构

与二叉堆相比,其优势是可以快速合并两个堆,因此它属于可合并堆 (mergeable heap) 抽象数据类型的一种

二项树递归定义如下:


二项堆是指满足以下性质的二项树的集合: 

以上第一个性质保证了二项树的根结点包含了最小的关键字。

第二个性质则说明结点数为 n 的二项堆最多只有 logn 棵二项树。实际上,包含n个节点的二项堆的构成情况,由n的二进制表示唯一确定,其中每一位对应于一颗二项树。例如,13的二进制表示为1101(2^3 + 2^2 + 2^0) 因此具有13个节点的二项堆由度数为3, 2, 0的三棵二项树组成

下图是含有13个节点的二项堆



参考:

wiki-二项堆

geeksforgeeks-binomial heap


上一篇: 堆-二叉堆
下一篇: 斐波那契堆
作者邮箱: 203328517@qq.com