二叉堆和二项堆有什么区别？

Question

二叉堆和二项堆有什么区别？

algorithmdata-structurespriority-queuebinary-heapbinomial-heap

22

我需要知道二叉堆和二项堆的主要区别，而不管它们结构上的差异，即二叉堆只能有两个孩子（树形表示），而二项堆可以有任意数量的孩子。

我实际上只是想知道，在将二项树结构组织成第一个孩子具有一个节点、第二个孩子具有两个节点、第三个孩子具有四个节点等等形式方面，有什么特殊之处？

如果我们使用一些没有限制两个孩子的普通树来进行堆，然后应用联合过程并将一个堆作为其他堆的左孩子，会发生什么？

- Abdul Samad

3

那么你将无法进行任何平衡操作，这些操作也无法在O(log n)时间内运行。查看二项堆的证明并找出它们会失败的位置。 - ShreevatsaR

3个回答

2

在templatetypedef提供的绝佳答案基础上，以下是一个图表，展示了不同操作的时间复杂度。

╔══════════════╦═══════════════════════╦════════════════════════╗
║  Operation   ║       Binary          ║      Binomial          ║
╠══════════════╬═══════════════════════╬════════════════════════╣
║              ║                       ║                        ║                              
║   insert     ║      O(logN)          ║      O(logN)           ║
║              ║                       ║                        ║                              
╠══════════════╬═══════════════════════╬════════════════════════╣
║  find Min    ║       O(1)            ║      O(logN)           ║
║              ║                       ║                        ║
╠══════════════╬═══════════════════════╬════════════════════════╣
║              ║                       ║                        ║
║   Revmove    ║       O(logN)         ║      O(logN)           ║
║              ║                       ║                        ║
╠══════════════╬═══════════════════════╬════════════════════════╣
║              ║                       ║                        ║
║ Decrease Key ║       O(logN)         ║      O(logN)           ║
║              ║                       ║                        ║
╠══════════════╬═══════════════════════╬════════════════════════╣
║              ║                       ║                        ║
║    Union     ║         O(N)          ║      O(logN)           ║
║              ║                       ║                        ║
╠══════════════╬═══════════════════════╬════════════════════════╣
║              ║ ■ Min element is root ║order k binomial tree Bk║
║              ║ ■ Heap height = logN  ║ ■ Number of nodes = 2k.║
║              ║                       ║ ■ Height = k.          ║                  
║              ║                       ║ ■ Degree of root = k.  ║
║  Useful      ║                       ║ ■ Deleting root yields ║
║  Properties  ║                       ║   binomial trees       ║
║              ║                       ║   Bk-1, … , B0.        ║
║              ║                       ║   (see graph below)    ║
║              ║                       ║                        ║
║              ║                       ║                        ║
║              ║                       ║                        ║
║              ║                       ║                        ║        
╚══════════════╩═══════════════════════╩════════════════════════╝

我从普林斯顿大学的讲义幻灯片中获得了这张图片。

二叉堆: (几乎完全二叉树)

二项堆:

- OLIVER.KOO

在二项堆中，节点的数量不是2k，而是2^k，对吗？ - undefined

1

通过将相同秩的任意两个子满二叉树连接到根节点上，可以创建一个二叉堆。它是一棵具有自由风格的树 - 一些叶子可以从右侧剪切。

秩为N的二项树不是一片森林。它是一个根节点，与之相连的是秩为N-1、N-2、...、1、0的二项树。二项堆是一棵具有绝对固定结构的树。

（恐怕有人以错误的方式阅读了维基百科。）
秩为k的二项树具有一个根节点，其子节点是秩为k-1、k-2、...、2、1、0的二项树的根节点（按此顺序）。

- Gangnus

请查看左上角的图片，这是关于二叉堆的维基百科页面：http://en.wikipedia.org/wiki/Binary_heap。我不是坚持认为维基百科是绝对权威，但你确定吗？ - Gangnus

那么，有什么区别吗？我们得到结果的方式不同吗？ - Gangnus

@Gangnus- 我同意二叉堆使用二叉树，但你不能只使用任何普通的二叉树，必须使用完全二叉树。此外，你不能像你建议的那样简单地合并两个完全二叉树，因为如果它们具有不同的高度，则合并后的树不一定是完全二叉树。尝试按照你的建议合并一个单节点和高度为100的完全二叉树；完成后它绝对不会是一个完全二叉树！ - templatetypedef

但是当你从底部剪掉一些叶子时，它也不是一个完全二叉树。 - Gangnus

让我们在聊天中继续这个讨论。 (Let us continue this discussion in chat.) - templatetypedef

显示剩余3条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

二叉堆和二项堆之间的关键区别在于它们的结构方式。在二叉堆中，堆是一棵单独的树，即完全二叉树。在二项堆中，堆是较小树的集合（即一组树的森林），每个树都是一个二项树。完全二叉树可以构建以容纳任意数量的元素，但某些阶数 n 二项树中的元素数量始终为 2^n。因此，我们只需要一个完全二叉树来支持二叉堆，但我们可能需要多个二项树来支持二项堆。有趣的是，二项堆中使用的二项树的阶数对应于森林中元素数量的二进制表示中设置的 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的二项树中节点的总数就是精确的2ⁿ。

你在最后一段描述的堆的想法并不总是能够获得高效的运行时间。特别地，如果你有分支因子巨大且没有其他结构约束的树，则在理论上可以建立一个由单个节点和（n - 1）个子节点组成的n个节点的堆。在这种情况下，在从堆中删除最小元素后，您必须查看所有n-1个子节点以确定哪一个是新的最小值，导致运行时间为O(n)。像完全二叉树、二项树等树的其他结构约束保证了这种最坏情况不会发生。

希望这有所帮助！