Пересечение двух максимальных куч

Question

У меня есть две максимальные кучи (представленные в массивах), H1 размера m и H2 размера n, с n>m. Я должен создать третью максимальную кучу с элементами, идущими от пересечения H1 и H2.

Элементарное решение (сканирование двух массивов) занимает время O(n*m) и не использует свойства max-heap.

Другие идеи?

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.

Answer 2

Если хеширование возможно, сделайте пересечение с установленным хешем, а затем сложите. Это O(n) с обычными оговорками.

Если хеширование невозможно, сделайте пересечение с деревом, установленным на H1 (меньшее из двух). Это O(n log m), что так же хорошо, как и при обычной нижней границе отличимости элементов.