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

问题描述

我需要知道二进制和二项堆之间的主要区别不管它们的结构差异的二进制堆只能有两个子（树重新presentation）和二项堆可以有任意数量的孩子。

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?

推荐答案

二叉堆和二项堆之间的主要区别是怎么堆的结构。在二元堆，堆是一棵树，这是一个完整的二叉树。在二项堆，堆是的集合的较小的树（即，一个的森林的树木），其中每一个二叉树。完全二叉树建成后可容纳任意数量的元素，但在一些n阶二叉树的元素个数为的总是 2 ^N 。因此，我们只需要一个完整的二叉树背二元堆，但我们可能需要备份一个二项堆多个二叉树。有趣的是，在一个二项式堆使用的二叉树的命令对应于1位在森林的元素数的二进制重新presentation设置

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.

原因组织二项堆，因为它们是，n阶二叉树永远都只有2 ^N 它节点。这让我们做出关于在二叉树的元素数量的假设，而不必实际检查该树的结构。另一方面，一些高度h的完整二进制树可以具有可变数目在它的节点取决于如何在最后一行被填写。每个孩子必须具有非常precisely定义的结构的事实，也可以用于证明孩子的数目至多为O（log n），其中n是在堆节点的总数，这意味着一个删除最小的成本并不太大。

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.

这背后一个重要的细节是，二项堆的没有的出现这种情况的K孩子树上。这是一个的严格定义为

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

• 序0二叉树是一个单一节点，
• n阶的二叉树与秩序0，1，2二叉树，...一个节点，N - 1儿童
。

（在技术上，为了0特例是没有必要在这里）。你可以在这里看到这样的：

(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:

• 序0二叉树是一个单一节点，
• n阶的二叉树是二阶二叉树N - 1，用树之一提出的其他的孩子
。

（花点时间看看为什么这些是等同的）。使用这个第二个定义，这是一个快速感应证据表明对节点树中的数目是2 ^N 。作为基础的情况下，秩序0一棵树有2 ⁰ = 1个节点的要求。对于感性一步，如果我们有秩序两棵树N - 1，他们总共有2 ^N-1 + 2 ^N-1 = 2 ^N 为所需的节点。因此，在n阶二叉树结点的总数恰好是2 ^N 。

(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ⁿ.

这个想法，你描述你的最后一段并不总是导致一个有效的运行时堆。特别是，如果你有一个庞大的分支因子并没有其他的结构限制的树木，那么你可以在理论上建立n个节点组成的一个节点与（N - 1）一堆孩子。在这种情况下，从堆中删除最小元素后，你不得不考虑所有N - 1的孩子，以确定哪些是新的最低，从而为O（n）的运行时间。像完整的二进制树，二叉树等树木等结构性制约因素保证这个最坏情况不会发生。

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.

希望这有助于！

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