algorithm - 二叉堆和二叉堆有什么区别？

Question

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

我实际上只是想知道以这样的方式组织二项式树结构有什么特别之处，即第一个孩子在一个节点上，第二个有两个，第三个有四个，依此类推？

如果我们对堆使用一些正常的树而没有两个孩子的限制，然后应用联合程序并只使一个堆成为其他堆的左孩子怎么办？

score 33 · Accepted Answer

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

按原样组织二项式堆的原因是，n 阶二项式树中始终恰好有 2 ^{n 个}节点。这使我们能够对二叉树中的元素数量做出假设，而无需实际检查该树的结构。另一方面，高度为 h 的完全二叉树可能具有可变数量的节点，具体取决于最后一行的填写方式。每个孩子必须有一个非常精确定义的结构这一事实也可以用来证明孩子的数量最多为 O(log n)，其中 n 是堆中的节点总数，这意味着delete-min 的成本不会太大。

这背后的一个重要细节是二项式堆不是任何恰好有 k 个孩子的树。这是一棵被严格定义为的树

0 阶二叉树是单个节点，并且
n 阶二叉树是具有 0、1、2、...、n - 1 阶二叉树作为子节点的单个节点。

（从技术上讲，这里不需要 order 0 特殊情况）。你可以在这里看到这个：

二叉树！

请注意，每个订单只有一棵树，节点的数量或位置完全没有灵活性。

然而，一个重要的替代定义如下：

0 阶二叉树是单个节点，并且
n阶二叉树是两棵n-1阶二叉树，其中一棵树是另一棵树的子树。

（花一点时间看看为什么这些是等价的）。使用第二个定义，它是一个快速归纳证明，表明树中的节点数是 2 ⁿ。作为基本情况，0 阶树有 2 个⁰ = 1 个所需的节点。对于归纳步骤，如果我们有两棵 n - 1 阶的树，它们根据需要共有 2 ^n-1 + 2 ^n-1 = 2 ^{n 个}节点。因此，n 阶二叉树中的节点总数正好是 2 ⁿ。

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

希望这可以帮助！

score 2 · Accepted Answer

添加上面由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)    ║
║              ║                       ║                        ║
║              ║                       ║                        ║
║              ║                       ║                        ║
║              ║                       ║                        ║        
╚══════════════╩═══════════════════════╩════════════════════════╝

我从普林斯顿讲座幻灯片中得到了这张图片

二叉堆：（几乎完全的二叉树）