关于合并两个堆的算法

Question

据我所知，存在一个二项堆或一个所谓的可合并堆，它用于合并两个堆。我的问题是，如果我将这两个堆复制到一个大阵列中，然后执行堆构建过程，而不是将这些堆合并为一个堆，那么这会是一个好方法吗？

因为我不知道如何通过堆操作使用两个堆来创建一个堆。请告诉我，如果这不是一个好方法，或者如果可以的话，请给我一些链接，其中实现了合并操作的二项堆。

Answer 1

如果你考虑一下，通过丢掉嵌入到其他堆的顺序中的所有信息创建一个堆不可能是最佳的。最糟糕的情况是，您应该将堆2中的所有项添加到堆1中，这只是从头开始创建全新堆的一半。

但事实上，你可以做的方式比那更好。合并两个格式良好的堆只涉及在另一个堆的树中找到其中一个根的插入点，并在该点插入它。没有进一步的工作是必要的，并且你已经完成了不超过ln N的工作！详细算法见here。

Answer 2

它会解决问题，它会给你一个正确的堆 - 但它不会有效。

创建[二进制] n元件的从头堆是O(n)，而merging 2现有二项堆是O(logn)。

Answer 3

合并2个二项堆的过程与合并排序中的合并操作非常相似。如果不知道合并 - 堆过程是个问题，以下步骤可能会有所帮助。

重复步骤1至4，直到堆之一是空的

1. 如果2堆的头部（这是二叉树）是相同程度，那么你具有更大分配堆的头用小钥匙作为堆头的小孩的钥匙。结果后一堆的头部的程度将增加1，并使前一堆的头部成为它当前头部的下一个元素，然后转到步骤2，否则，如果它们的程度不同，则转到步骤4

2. 如果头部和在步骤1后堆的下一个二叉树是相同程度的，则转到步骤3否则到步骤1

3. 联合头部和堆中的下一个元素，在与步骤1中所做的相同，然后将新的组合二叉树作为头并转至步骤2.

4. 查看2个堆中的哪个具有较低等级的头。分配这个堆的头部作为其他堆的头部和从堆中删除它最初存在

Answer 4

Brodal队列和Brodal-Okasaki队列（自举歪斜二项堆）得到最好的最坏情况下的渐近界对于可合并的堆，支持O（1）插入，合并和findMin以及O（log n）deleteMin。 Brodal队列是短暂的，并且支持高效的删除和减少键。 Brodal-Okasaki队列是持久的（实际上是纯粹的功能），但不支持删除或减少键。不幸的是，Brodal和Okasaki说这两种实现在实践中都是低效的，Brodal认为他的队列太复杂，无论如何都不实用。

斐波纳契堆给出了类似的摊销（但不是最坏的情况下）的界限，并且在摊销情况下可能更有效和实用。配对堆是另一个不错的选择：根据维基百科，它们的确切范围是未知的，但它们在实践中表现得非常好。