两个最大堆的交集

Question

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

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

还有其他想法吗？

- Davide R.

---

“O(nlogn + mlogm)” 可以很容易地实现，显然。不知道是否有类似于合并两个排序数组的线性解决方案。 - amit

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.

- rob mayoff

Answer 2

如果可以进行哈希，使用哈希集合进行交集操作，然后进行堆化。这个方法的时间复杂度为O(n)，但需要注意一些常见陷阱。

如果无法进行哈希，使用树集合在H1（两者中较小的一个）上进行交集操作。这种方法的时间复杂度为O(n log m)，这已经是通常元素不同性的下限了。

- David Eisenstat

---

你能解释一下吗？哈希O(m+n)，交集O(m)，堆化O(mlgm)，求和O(n+mlgm)。为什么这是线性的？ - Jason Hu

@HuStmpHrrr，你忘记了线性时间的自底向上堆化。 - harold

@harold 哦糟糕。记忆不好。 - Jason Hu