logo标签列表

合并两个最大堆的算法？

algorithmdata-structuresmergeheap
34

有没有一种高效的算法可以合并以数组形式存储的两个最大堆？

13
好的，您尝试过什么了吗？ - Jonathan Feinberg
将注释放在问题内部，这样可以表明您已经思考过该问题，并对除平凡解决方案以外的解决方案感兴趣。 - Konrad Rudolph
2
@Yaron：你可以在O（N + k）的时间内构建新堆。只需将数组连接起来，然后使用默认方法构建新堆即可。 - Alexandru
默认方法是什么？我猜默认方法的时间复杂度为O(n log n)，而不是O(N+k)。 - Arian
@ArianHosseinzadeh 默认的堆化方法接受一个大小为n的数组，并在O(n)时间内构建一个堆。 - Larry
显示剩余3条评论
3个回答
23

这取决于堆的类型。

如果它是标准堆，其中每个节点最多有两个子节点，并且叶子节点最多在两个不同的行上，那么您无法获得比O（n）更好的合并结果。

只需将两个数组放在一起，并创建一个新的堆，需要O（n）的时间。

为了获得更好的合并性能，您可以使用另一种堆变体，例如Fibonacci堆，其摊销为O（1）。

更新：请注意，单独将第一个堆的所有元素插入第二个堆或反之亦然比较差，因为插入需要O（log n）。

  1. 创建一个数组，并以任意顺序将两个堆的元素放入其中
  2. 现在从最低层开始。最底层包含大小为1的微不足道的最大堆，因此此级别已完成
  3. 向上移动一个级别。当“子堆”之一的堆条件被违反时，请使用其较大的子节点交换“子堆”的根。之后，第2级别就完成了
  4. 移动到第3级别。当堆条件被违反时，请像之前处理。与其较大的孩子交换并递归处理，直到所有内容都匹配到第3级别
  5. ...
  6. 当您到达顶部时，您创建了一个新堆，需要O（n）的时间。

我在此省略了证明，但您可以解释一下，因为您已经完成了大部分在底层堆上的工作，在那里您不必交换太多内容以重新建立堆条件。您已经对较小的“子堆”进行了操作，这比如果您将每个元素插入一个堆中要好得多=>然后，您每次都会对整个堆进行操作，这需要O（n）的时间。

更新2：二项式堆允许在O（log（n））中合并，并且符合您的O（log（n）^ 2）要求。

“你不能在合并操作中获得比O(n)更好的性能”--这里的n是什么？O(n)又代表什么？如果你只是简单地将两个数组放在一起并重建堆，那么使用的比较次数（和数据移动）肯定可以更少。 - Alexey
10
10
要实现这一点，需要像普通的基于指针的树一样使用指针来实现堆，这与常见做法不同。 - phoeagon
我本来也想说同样的话，@phoeagon - 我开始阅读它时发现它在将一个数组复制到另一个数组时需要O(k)数据操作，但在论文的最后指出，如果使用指针而不是基于数组的堆，则可以在常数时间内完成数据操作，使您回到O(log n * log k)操作。 - Asaf
1
我认为在这种情况下你需要的是一个二项堆。
二项堆是二项树的集合，属于可合并堆家族。当对具有n个元素的2个或多个二项堆进行联合（合并）时，最坏情况运行时间为O(lg n)。
更多信息请参见http://en.wikipedia.org/wiki/Binomial_heap。
二项堆不以数组形式存储。 - Tomer Wolberg
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接