合并两个二进制最大堆，其中一个堆中的所有元素都大于另一个堆中的所有元素？

Question

我遇到了这个编程面试问题，我不确定我的答案是否正确。我找不到这个问题的正确答案。这是问题，

Let H1 and H2 be two (binary) max-heaps with n1 and n2 elements respectively. If every element in H1 is larger than every element in H2, design an algorithm that merges these two heaps into one (binary) max-heap in O(n2) time (assume that both H1 and H2 are large enough to hold n1 + n2 elements)

所以，我在想，既然H1中的每个元素都大于H2中的每个元素，那么我们可以将合并后的最大堆存储在H1中。所以，我们所要做的就是简单地从 H2 中获取第一个元素，在 H2 数组中的位置 0，然后将该元素插入到 H1 中，附加到 H1 数组的末尾，使其成为 H1 中的叶子。我们可以对 H2 中的每个元素连续这样做。我想一旦我们开始将 H2 中的元素作为子元素添加到 H2 的元素中，那么我们将不得不开始检查该子元素是否小于父元素，如果不是，我们将交换它们。我假设由于添加一个元素而不调用 heapify 并在必要时进行交换会给我们带来 O(n2) 的复杂性。

那么，我的解法准确吗？如果没有任何帮助，我们将不胜感激。如果我的解决方案的任何部分不清楚，请告诉我，以便我澄清。

Answer 1

您通常不能将 H2 附加到 H1 上，因为正如评论中指出的那样，这样做会产生无效的堆。这种情况并不少见。

例如，假设有两个最大堆：

h1 = [100]
h2 = [6,3,5,1,2,4]

    h1        h2

   100        6
            3   5
           1 2 4

如果你只是将 h2 附加到 h1，你会得到：

    100
  6    3
 5 1  2 4

这显然是无效的，因为 4 是 3 的 child。

如果h1=[100,98]，同样的事情会发生：

       100
    99     6
   3  5  1   2
 4

您需要做的是将 h2 附加到 h1，然后运行一个缩写的 build-heap 重新排列 h2 中的项目以反映其新的堆中的位置。您已经知道您从 h2 添加的所有项目都小于 h1 中的最小项目，因此您不必触摸 h1 中的任何项目。

这与标准 build-heap 的唯一区别是起始位置和结束位置。基本上，您从 h2 的中间开始，然后向后工作到 h2 的开头。

h1_length = h1.length
h2_length = h2.length
h1.array.append(h2.array)  // copies items from h2 to h1
// rearrange h2 items
start = h1_length + (h2_length/2)
for (item = start; item > h1_length; --item)
{
    i = item
    // This assumes that the root of the heap is at 0.
    // If the root is at 1, then the left child is at i*2
    while (i*2+1 < h1.length)
    {
        // get the largest child of this item
        leftChildIndex = i*2+1
        rightChildIndex = leftChildIndex + 1
        largestChildIndex = leftChildIndex
        if (rightChildIndex < h1.length &&
            h1.array[rightChildIndex] > h1.array[leftChildIndex)
        {
            largestChildIndex = rightChildIndex
        }
        // if the item is greater than or equal to its largest child,
        // then the item is where it belongs.
        if (h1.array[i] >= h1.array[largestChildIndex])
        {
            break;
        }
        // swap the item with its child, and check again
        swap(h1.array[i], h1.array[largestChildIndex])
        i = largestChildIndex
    }
}

build-heap 算法被证明是 O(n)，其中 n 是您正在构建的堆中的项目数。由于您只处理 h2.length 项，因此这将花费 O(h2.length) 时间。

合并两个二进制最大堆，其中一个堆中的所有元素都大于另一个堆中的所有元素？

Merging two binary max heaps in which all the elements in one heap is greater than all the elements in the other?

algorithm

heap

data-structures