是否可以在不重新构建堆的情况下从两个堆构建最大堆？

Question

我最近参加了我的计算机科学考试，有一个类似的问题。

有两个最大堆(数组已实现)。您需要想出一个算法来合并这两个最大堆，并创建一个新的max堆(数组已实现)。

这个问题的解决是非常直观的，即：

1. 合并两个数组
2. 调用堆重建

我在互联网上看到了同样的解决方案。

然而，我写了一个这样的解决方案，我无法反驳自己的。

我的算法

一个新的堆数组，大小为heapArr1.size + heapArr2

• Create，循环

• 比较heapArr1的index1元素和heapArr2

• Whichever的index2元素，写入结果数组并增加元素的索引，直到两个数组都被遍历。

例如

Heap1: 12-5 -6-2-3

Heap2: 15-13-4-1-0

我们首先比较15和12。写15。

resultHeap: 15

现在比较13和12

resultHeap: 15-13

比较4和12

resultHeap: 15-13- 12

比较4和5

resultHeap: 15-13- 12 - 4

如果我们继续这样下去

resultHeap: 15 - 13 - 12 -5-6-4-2-3- 0.它也是一个堆。

这个算法正确吗？或者有人能给出反驳数据集？

Answer 1

对于同样大小的堆，这可能是一个可能的解决方案。

1. 假定2最大(或最小)二进制堆(A和B)。
2. 首先比较根，其中一个较小的(假设A)可以安全地假定为另一个(B)的子树的候选。因此，将其赋值为B (假设为左)
3. 的任何一个子级，因为B的孩子现在正在被替换，您有两个新堆要考虑，即B的原始子女
4. ，现在您有一个空空间，也就是B的右子空间。按照这个过程递归地合并B的孩子，并分配结果堆作为B

的右子。

这只是一个花哨的指针操作，它实际上并不是在构建堆，而是利用已经有堆的事实。

对未能更正式地表达这一观点表示歉意。如果你发现有什么问题，请纠正我。这只是一般的想法，并没有考虑具体的实现细节。