我需要知道二进制堆和二项式堆之间的主要区别，无论它们的结构差异是什么，即二进制堆只能有两个子代(树表示)，而二项堆可以有任意数量的子代。
我实际上只是想知道，以这样的方式组织二叉树的结构有什么特别之处，以至于第一个 child 在一个节点上有第二个 child 在三个节点上有四个，依此类推？
如果我们在不限制两个 child 的情况下对堆使用一些普通树，然后应用联合过程并将一个堆作为其他堆的左 child ，该怎么办？
最佳答案
二进制堆和二项式堆之间的主要区别在于堆的结构。在二进制堆中，堆是一棵树，这是一棵完整的二进制树。在二项式堆中，堆是较小树(即树的森林)的集合，每棵都是二项树。可以构建完整的二叉树来容纳任意数量的元素，但是某个n阶二项式树中的元素数量始终为2n。因此，我们只需要一个完整的二叉树来支持二进制堆，但是我们可能需要多个二叉树来支持二叉堆。有趣的是，二项式堆中使用的二项式树的顺序对应于森林中元素数量的二进制表示形式中设置的1位。
之所以要组织二项式堆，是因为n阶的二项式树中始终总是有2n个节点。这使我们可以对二叉树中的元素数量进行假设，而无需实际检查该树的结构。另一方面，高度为h的完整二叉树中可能有可变数量的节点，具体取决于最后一行的填充方式。每个子代必须具有非常精确定义的结构这一事实也可以用来证明子代的数量最多为O(log n)，其中n是堆中节点的总数，这意味着删除分钟的成本不会太大。
这背后的一个重要细节是，二项式堆不是碰巧有k个 child 的任何树。这是一棵严格定义为的树
(从技术上讲，这里不需要0阶特殊情况)。您可以在这里看到:
请注意，每个顺序只有一棵树，节点的数量或位置完全没有灵活性。
但是，一个重要的替代定义如下:
(花点时间看一下为什么它们相等)。使用第二个定义，它是一个快速的归纳证明，它表明树中的节点数为2n。作为基本情况，顺序为0的树根据需要具有20 = 1个节点。对于归纳步骤，如果我们有n-1阶的两棵树，则它们根据需要共同具有2n-1 + 2n-1 = 2n个节点。因此，n阶二叉树中的节点总数恰好是2n。
您在最后一段中描述的堆的想法并不总是导致有效的运行时。特别是，如果您的树木具有很大的分支因子，并且没有其他结构性约束，那么理论上您可以构建n个节点的堆，其中n个节点由具有(n-1)个子节点的单个节点组成。在这种情况下，从堆中删除最小元素后，您必须查看所有n-1个子元素，以确定哪个是新的最小元素，并给出O(n)的运行时间。诸如完整的二叉树，二项式树等其他对树的结构性约束保证了这种最坏情况不会发生。
希望这可以帮助!