CODEWITHSUNDEEP
algorithmheapset-intersection
Davide R.
Davide R.

Reputation: 207

Intersection of two maximum heaps

I have two maximum-heaps (represented in arrays), H1 of size m and H2 of size n, with n>m. I have to create a third max-heap with elements coming from the intersection of H1 and H2.

The elementary solution (scan the two arrays) takes O(n*m) time, and doesn't take advantage of the max-heap properties.

Other ideas?

Upvotes: 3

Views: 872

Answers (2)

David Eisenstat
David Eisenstat

Reputation: 65458

If hashing is possible, do the intersection with a hash set and then heapify. This is O(n) with the usual caveats.

If hashing is not possible, do the intersection with a tree set on H1 (the smaller of the two). This is O(n log m), which is as good as it gets by the usual element distinctness lower bound.

Upvotes: 2

rob mayoff
rob mayoff

Reputation: 385670

Given two heaps, you can compute the intersection of elements in O(M log M + N log N) time, and the result is ordered. An ordered array is already a heap, so no further time is required.

Python-syntax example:

# 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.

Upvotes: 2

Related Questions