二叉堆和二叉堆有什么区别? [英] What is the difference between binary heaps and binomial heaps?

问题描述

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

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ⁿ.因此，我们只需要一个完整的二叉树来支持一个二叉堆，但我们可能需要多个二叉树来支持一个二项堆.有趣的是，二项式堆中使用的二项式树的阶对应于森林中元素数量的二进制表示中设置的 1 位.

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ⁿ 个节点.这使我们可以对二叉树中的元素数量做出假设，而无需实际检查该树的结构.另一方面，某个高度为 h 的完整二叉树中可能有可变数量的节点，具体取决于最后一行的填充方式.每个子节点必须具有非常精确定义的结构这一事实也可以用来证明子节点的数量最多为 O(log n)，其中 n 是堆中的节点总数，这意味着一个delete-min的代价不算太大.

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ⁿ.作为基本情况，0 阶树根据需要具有 2⁰ = 1 个节点.对于归纳步​​骤，如果我们有两棵 n - 1 阶的树，它们总共有 2^n-1 + 2^n-1 = 2ⁿ 节点根据需要.因此，n 阶二叉树中的节点总数正好是 2ⁿ.

(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 - 1) 个子节点的单个节点组成的 n 个节点的堆.在这种情况下，从堆中删除最小元素后，您必须查看所有 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屋！