二进制堆和二项式堆有什么区别？

Question

我需要知道二进制和二进制堆之间的主要区别,不管它们的结构差异,二元堆只能有两个子(树表示),二项堆可以有任意数量的子.

我实际上只是想知道组织二项式树结构的特别之处在于第一个孩子在一个节点上有第二个有两个第三个有四个等等吗？

如果我们使用一些普通的树而没有两个孩子的限制然后应用联合过程而只是让一个堆成为其他堆的左子？

Answer 1

二进制堆和二进制堆之间的关键区别在于堆的结构.在二进制堆中,堆是单个树,这是一个完整的二叉树.在二项堆,堆是一个集合的较小的树(即森林树木),每一个都是一个二叉树.可以构建完整的二叉树来保存任意数量的元素,但是某个阶n的二叉树中的元素数总是 2 ⁿ.因此,我们只需要一个完整的二叉树来支持二进制堆,但是我们可能需要多个二叉树来支持二项式堆.有趣的是,二项式堆中使用的二叉树的顺序对应于森林中元素数量的二进制表示中设置的1位.

组织二项式堆的原因是,n阶二叉树总是正好有2 ^n个节点.这允许我们对二叉树中的元素数量进行假设,而不必实际检查该树的结构.另一方面,某个高度为h的完整二叉树可能在其中具有可变数量的节点,具体取决于最后一行的填充方式.每个子节点必须具有非常精确定义的结构这一事实也可用于证明子节点数最多为O(log n),其中n是堆中节点的总数,这意味着删除分钟的成本不是太大.

这背后的一个重要细节是二项式堆不是碰巧有k个孩子的任何树.这是一棵严格定义为的树

• 0阶的二叉树是单个节点,和
• n阶二叉树是单个节点,其二项式树为0,1,2,...,n - 1作为子节点.

(从技术上讲,此处不需要订单0特殊情况).你可以在这里看到:

请注意,每个订单只有一棵树,在节点的数量或位置上根本没有灵活性.

但是,一个重要的替代定义如下:

• 0阶的二叉树是单个节点,和
• n阶二叉树是两个二阶树,阶数为n - 1,其中一棵树是另一棵树的子项.

(花点时间看看为什么这些是等价的).使用第二个定义,它是一个快速的感应证明,表明树中的节点数是2 ⁿ.作为基本情况,0阶的树根据需要具有2 ⁰ = 1个节点.对于归纳步​​骤,如果我们有两个n-1阶的树,则它们根据需要共同具有2 ^n-1 + 2 ^n-1 = 2 ^n个节点.因此,n阶二叉树中的节点总数恰好是2 ⁿ.

您在最后一段中描述的堆的想法并不总是导致高效的运行时.特别是,如果您的树具有巨大的分支因子而没有其他结构约束,那么理论上您可以构建一个由n个节点组成的堆,这些节点由具有(n-1)个子节点的单个节点组成.在这种情况下,在从堆中删除最小元素之后,您必须查看所有n - 1个子节点以确定哪个是新的最小值,从而给出O(n)的运行时间.对完整二叉树,二叉树等树的其他结构约束保证了最坏情况不会发生.

希望这可以帮助!