二进制堆和二项式堆之间有什么区别？ [英] What is the difference between binary heaps and binomial heaps?

问题描述

我需要知道二进制和二进制堆之间的主要区别，无论它们的结构差异如何，二进制堆只能有两个子代（树表示），二项式堆可以有任何数量的子代。

我实际上只是想知道如何组织二项式树结构，使得第一个孩子在一个节点上有二分之二有四个等等？

如果我们在没有两个孩子的限制的情况下使用一些正常的树，然后应用联盟过程，并且只剩下一堆剩下的另一个堆的左边的小孩？

解决方案

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

组织二项式堆的原理是，n阶二叉树总是在其中正好有2个节点。这允许我们假设二项式树中的元素的数量，而不需要检查该树的结构。另一方面，某个高度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 < sup>节点。因此，n阶的二项式树中的节点总数正好是2 n 。}

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

希望这有帮助！

I need to know the main difference between binary and binomial heaps regardless of the their structure difference that binary heaps can have only two child (tree representation) and binomial heaps can have any number of children.

I am actually just wondering that what so special in organizing the binomial tree structure in such a way that the first child have on one node second have two third have four and so on?

What if, if we use some normal tree for heaps without restriction of two child and then apply the union procedure and just make one heap the left child of the other heaps?

解决方案

The key difference between a binary heap and a binomial heap is how the heaps are structured. In a binary heap, the heap is a single tree, which is a complete binary tree. In a binomial heap, the heap is a collection of smaller trees (that is, a forest of trees), each of which is a binomial tree. A complete binary tree can be built to hold any number of elements, but the number of elements in a binomial tree of some order n is always 2ⁿ. Consequently, we only need one complete binary tree to back a binary heap, but we may need multiple binomial trees to back a binomial heap. Interestingly, the orders of the binomial trees used in a binomial heap correspond to the 1 bits set in the binary representation of the number of elements in the forest.

The reason for organizing binomial heaps as they are is that a binomial tree of order n always has exactly 2ⁿ nodes in it. This allows us to make assumptions about the number of elements in the binomial tree without actually having to inspect the structure of that tree. On the other hand, a complete binary tree of some height h may have a variable number of nodes in it depending on how the last row is filled out. The fact that each of the children must have a very precisely-defined structure can also be used to prove that the number of children is at most O(log n), where n is the total number of nodes in the heap, which means that the cost of a delete-min is not too large.

An important detail behind this is that a binomial heap is not any tree that happens to have k children. It's a tree that's rigorously defined as

• The binomial tree of order 0 is a single node, and
• The binomial tree of order n is a single node with binomial trees of order 0, 1, 2, ..., n - 1 as children.

(Technically, the order 0 special case isn't necessary here). You can see this here:

Note that there is exactly one tree of each order, with no flexibility at all in the number or position of the nodes.

However, an important alternative definition is the following:

• The binomial tree of order 0 is a single node, and
• The binomial tree of order n is two binomial trees of order n - 1, with one of the trees made a child of the other.

(Take a minute to see why these are equivalent). Using this second definition, it's a quick induction proof to show that the number of nodes in the tree is 2ⁿ. As a base case, a tree of order 0 has 2⁰ = 1 nodes as required. For the inductive step, if we have two trees of order n - 1, they collectively have 2^n-1 + 2^n-1 = 2ⁿ nodes as required. Thus the total number of nodes in a binomial tree of order n is exactly 2ⁿ.

The idea for a heap that you're describing in your final paragraph does not always lead to an efficient runtime. In particular, if you have trees with a huge branching factor and no other structural constraints, then you could in theory build a heap of n nodes consisting of a single node with (n - 1) children. In that case, after deleting the minimum element from the heap, you'd have to look at all n - 1 children to determine which was the new minimum, giving a runtime of O(n). The other structural constraints on trees like complete binary trees, binomial trees, etc. guarantee that this worst-case doesn't happen.

Hope this helps!

这篇关于二进制堆和二项式堆之间有什么区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！