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

Question

我最近参加了计算机科学考试，出现了这样的一道题。

There are two max-heaps (array implemented). You need to come up with an algorithm that merges these two max-heaps and creates a new max-heap (array implemented)

题解很直观就是：

合并两个数组
调用堆重建

我在 Internet 上查找并遇到了相同类型的解决方案。

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

我的算法

Create index1 and index2 which points first element of heapArr1 and heapArr2

Create a new heap array which has size of heapArr1.size + heapArr2.size

In while loop

compare index1 element of heapArr1 and index2 element of heapArr2

Whichever is greater, write the result array and increment the index of the array that element taken until two arrays all traversed.

例如

Heap1: 12-5 -6-2-3

Heap2: 15-13-4-1-0

我们先比较15和12，写15

结果堆：15

现在比较 13 和 12

结果堆：15 - 13

比较 4 和 12

resultHeap: 15 - 13 - 12

比较 4 和 5

结果堆：15 - 13 - 12 - 4

如果我们继续这样下去，我们有

resultHeap: 15 - 13 - 12 - 5 - 6 - 4 - 2 - 3 - 1 - 0。而且还是堆

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

Answer 1

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

假设 2 个最大（或最小）二进制堆（A 和 B）。
首先比较根，较小的那个（假设A）可以安全地假设为另一个（B）的子树的候选者，因此将其分配为B的任何一个child （假设左边）
由于 B 的 children 现在被替换了，你有 2 个新堆需要考虑，即 B 的原始 children
现在你有一个空的space，即B的右边child。关注此过程递归地合并 B 的子节点并将生成的堆分配为 B 的右 child。

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

抱歉无法更正式地表达。如果您发现错误，请纠正我。这只是总体思路，并未考虑具体实施细节。

Answer 2

Is this algorithm correct?

没有

can someone gave the refutation data set?

接受这个输入：

第一个堆：10、2、9
```
    10
   /  \
  2    9
```
第二堆：8、1、4
```
    8
   / \
  1   4
```

应用算法--括号中表示每个堆中的current索引：

Heap 1	Heap 2	Result heap
[10],2,9	[8],1,4	10
10,[2],9	[8],1,4	10,8
10,[2],9	8,[1],4	10,8,2
10,2,[9]	8,[1],4	10,8,2,9 (violation)
10,2,9[]	8,[1],4	10,8,2,9,1
10,2,9[]	8,1,[4]	10,8,2,9,1,4 (violation)

结果不是有效堆，因为 9 不应该是 8 的 child，因为 9 更大。并且 4 不应该是 2 的 child，因为 4 更大。

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

Is it possible to build a max heap from two heap without rebuilding the heap?

algorithm

heap

max-heap