algorithm - 两个最大堆的交集

Question

我有两个最大堆(用数组表示)，大小为 m 的 H1 和大小为 n 的 H2，其中 n>m。我必须创建第三个最大堆，其中的元素来自 H1 和 H2 的交集。

基本解决方案(扫描两个数组)需要 O(n*m) 时间，并且没有利用最大堆属性。

其他想法？

Answer 1

给定两个堆，您可以在 O(M log M + N log N) 时间内计算元素的交集，并且结果是有序的。有序数组已经是堆，因此不需要更多时间。

Python 语法示例:

# Given arrays heap1, heap2.

intersection = []
while len(heap1) > 0 and len(heap2) > 0:
    if heap1[0] == heap2[0]:
        # Common element, part of the intersection.
        intersection.append(heap1[0])
        heap.heappop(heap1)
        heap.heappop(heap2)
    elif heap1[0] > heap2[0]:
        heap.heappop(heap1)
    else:
        heap.heappop(heap2)

# intersection now contains the common elements of heap1 and heap2,
# in max-to-min order, so it already meets the heap invariant.