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

Question

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

有两个最大 - 蜂座（已实现数组）。您需要提出一种算法 合并这两个Max-Heaps，并创建一个新的Max-Heap（已实现的数组）

问题的新的Max-Heap（Array实现）解决方案非常直观，这是：

1. 合并
2. 两个阵列调用堆重建

我在Internet中看到的

，并遇到了相同类型的解决方案。但是，我写了一个类似的解决方案，我无法自己驳斥自己的解决方案。

我的算法

1. 创建index1和index2，该指向heaparr1和heaparr2的第一个元素
2. 创建一个新的堆数组，该数组的大小为HeaParr1.size + Heaparr22.Size
3. 在循环中
4. 比较heaparr1和heaparr2元素的索引元素
5. 以更大为准，写入结果数组并递增该数组所采集的数组的索引，直到两个数组全部遍历。

例如

heap1：12-5 -6-2-3

heap2：15-13-4-1-0

我们将首先比较15和12

。

HEAP2 ： EM>现在比较13和12

resultheap：15-13

比较4和12

resultheap：15-13-13-12

比较4和5

resultheap：15-13-12-4

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

resultheap ：15-13-13-12 -5-6-4-2-2-3-1-1-0。它也是堆

该算法正确吗？还是有人可以提供反驳数据集？

Answer 1

此算法正确吗？

不。

有人可以提供反驳数据集吗？

进行此输入：

• 第一个堆：10、2、9

    10
     / \
    2 9
   

• 第二堆：8、1、4

    8
     / \
    1 4
   

应用算法 - 括号指示每个堆中的电流索引：

堆1	堆2	结果堆
[10]，2,9	[8]，1,4，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]，[1]，[1]，[1]， 4	10,8,2,9（违法）
10,2,9 []	8，[1]，4	10,8,2,9,1
10,2,9 [] []	8,1，[4]	10， [4] 10，10 8,2,9,1,4（违规）

      10
     /   \
    8     2
   / \   /
  9   1 4 

结果不是有效的堆，因为9不应是8个孩子，因为9更大。 4不应该是2的孩子，因为4更大。

Answer 2

这可能是尺寸相等的堆的可能解决方案。

1. 假设2最大（或min）二进制堆（A和B）。
2. 首先比较根，一个较小的根（假设a）可以安全地假定为另一个子树的候选者（b），因此将其分配为B的任何一个孩子（假设左），
3. 因为B的孩子现在是B的被替换，您有2个新堆考虑IE B的原始孩子
4. ，现在您有一个空白的空间，即合适的孩子。
   此过程递归将B的Chilren合并，并将结果堆分配为B的合适孩子。

这只是花哨的指针操纵，实际上并没有构建堆，而是利用您已经拥有堆的事实。

道歉，无法更形式地表达它。如果您发现有问题，请纠正我。这只是一般的想法，不考虑实施具体的细节。