0

据我所知，存在一个二项式堆或所谓的可合并堆，用于合并两个堆。我的问题是，如果我将这两个堆复制到一个大数组中然后执行堆构建过程，而不是将这些堆动态合并到一个堆中，这是否是一个好方法？

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

4

4 回答 4

1

如果您考虑一下，通过丢弃嵌入在其他堆排序中的所有信息来创建一个堆不可能是最佳的。最坏的情况是，您应该将堆 2 中的所有项目添加到堆 1，而这只是从头开始创建全新堆的一半工作。

但事实上，你可以做得比这更好。合并两个格式良好的堆只不过是在另一个堆的树中找到一个根的插入点，然后将其插入该点。没有进一步的工作是必要的，你所做的只是ln N工作！详细算法见这里。

于 2012-03-17T20:28:15.173 回答
1

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

n从头开始创建元素的 [二进制] 堆是O(n)，而合并2 个现有的二项式堆是O(logn)。

于 2012-03-17T20:28:22.287 回答
0

Brodal 队列和 Brodal-Okasaki 队列（自举倾斜二项式堆）为可合并堆提供了最佳的最坏情况渐近边界，支持 O(1) 插入、合并和 findMin 以及 O(log n) 删除Min。Brodal 队列是临时的，并且支持高效的 delete 和 reductionKey。Brodal-Okasaki 队列是融合持久的（实际上纯粹是功能性的），但不支持 delete 或 reduceKey。不幸的是，Brodal 和 Okasaki 说这两种实现在实践中都效率低下，而且 Brodal 认为他的队列太复杂，在任何情况下都不实用。

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

于 2012-07-13T22:28:51.083 回答
0

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

重复步骤 1 到 4，直到其中一个堆为空

  1. 如果 2 个堆的头（二叉树）的度数相同，那么您将具有较大键的堆的头分配为具有较小键的堆头的孩子的孩子。因此后一个堆的头的度数将增加1，使前一个堆的头成为其当前头的下一个元素，然后转到步骤2，否则如果它们的度数不同，则转到步骤4

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

  3. 以与步骤 1 中相同的方式组合堆中的头部及其下一个元素，并将新的组合二叉树分配为头部，然后转到步骤 2。

  4. 查看 2 个堆中哪个堆的头部程度较低。将此堆的头部分配为其他堆的头部，并将其从最初存在的堆中删除

于 2012-03-23T14:35:18.340 回答