合并两个完美的二叉堆？

Question

6

我卡在一个问题上一段时间了，想知道是否有人可以指点一下:

假设使用基于指针的树表示法而不是数组表示法来表示二叉堆。考虑将二叉堆LHS与RHS合并的问题。假设两个堆都是满完全树，分别包含(2^L - 1)和(2^R -1)个节点。
给出两个O(log N)算法来合并这两个堆，一个是当L = R时，另一个是当|L - R| = 1时。

这是一道作业问题，我只需要被指引正确的方向。

- user220755

LHS树需要从左边开始吗，还是这只是为了方便而命名的？ - outis

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- outis · Accepted Answer

5

当L=R时的提示：假装你刚刚删除了根节点。如果需要更多帮助，请告诉我。

- outis

这是一个很好的提示。我想不明白的是，教授用 |L-R| = 1 意味着什么？看起来你的提示得出的算法在那种情况下也能工作。 - PeterAllenWebb

1

考虑基于数组的堆的属性，以及如果|L-R|=1，则所暗示的算法将违反这些属性中的一些。实际上，不仅仅是基于数组的堆；还要考虑形状属性。 - outis

我无法理解这个提示，请进一步解释。 - Anirudh