合并两个最大堆的算法?

发布于 08-08 03:42 字数 34 浏览 8 评论 0 原文

是否有一种有效的算法来合并存储为数组的 2 个最大堆?

Is there an efficient algorithm for merging 2 max-heaps that are stored as arrays?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

白馒头 2024-08-15 03:42:10

这取决于堆的类型。

如果它是一个标准堆,其中每个节点最多有两个子节点,并且叶子节点最多位于两个不同的行上,那么您无法获得比 O(n) 更好的合并效果。

只需将两个数组放在一起并创建一个新的堆,这需要 O(n) 的时间。

为了获得更好的合并性能,您可以使用另一种堆变体,例如斐波那契堆,它可以按 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) 要求。

It depends on what the type of the heap is.

If it's a standard heap where every node has up to two children and which gets filled up that the leaves are on a maximum of two different rows, you cannot get better than O(n) for merge.

Just put the two arrays together and create a new heap out of them which takes O(n).

For better merging performance, you could use another heap variant like a Fibonacci-Heap which can merge in O(1) amortized.

Update:
Note that it is worse to insert all elements of the first heap one by one to the second heap or vice versa since an insertion takes O(log(n)).
As your comment states, you don't seem to know how the heap is optimally built in the beginning (again for a standard binary heap)

  1. Create an array and put in the elements of both heaps in some arbitrary order
  2. now start at the lowest level. The lowest level contains trivial max-heaps of size 1 so this level is done
  3. move a level up. When the heap condition of one of the "sub-heap"s gets violated, swap the root of the "sub-heap" with it's bigger child. Afterwards, level 2 is done
  4. move to level 3. When the heap condition gets violated, process as before. Swap it down with it's bigger child and process recursively until everything matches up to level 3
  5. ...
  6. when you reach the top, you created a new heap in O(n).

I omit a proof here but you can explain this since you have done most of the heap on the bottom levels where you didn't have to swap much content to re-establish the heap condition. You have operated on much smaller "sub heaps" which is much better than what you would do if you would insert every element into one of the heaps => then, you willoperate every time on the whole heap which takes O(n) every time.

Update 2: A binomial heap allows merging in O(log(n)) and would conform to your O(log(n)^2) requirement.

他夏了夏天 2024-08-15 03:42:10

大小为 n 和 k 的两个二进制堆可以在 O(log n * log k) 比较中合并。请参阅

Jörg-R。 Sack 和 Thomas Strothotte,合并堆的算法,Acta Informatica 22 (1985), 172-186。

Two binary heaps of sizes n and k can be merged in O(log n * log k) comparisons. See

Jörg-R. Sack and Thomas Strothotte, An algorithm for merging heaps, Acta Informatica 22 (1985), 172-186.

世界如花海般美丽 2024-08-15 03:42:10

我认为在这种情况下您要寻找的是二项式堆。

二项式堆是二项式树的集合,是可合并堆家族的成员。在堆中总共有 n 个项目的 2 个以上二项式堆上进行联合(合并)的最坏情况运行时间是 O(lg n)。

有关详细信息,请参阅 http://en.wikipedia.org/wiki/Binomial_heap

I think what you're looking for in this case is a Binomial Heap.

A binomial heap is a collection of binomial trees, a member of the merge-able heap family. The worst-case running time for a union (merge) on 2+ binomial heaps with n total items in the heaps is O(lg n).

See http://en.wikipedia.org/wiki/Binomial_heap for more information.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文