Поддержание инварианта в алгоритме Прима

Question

Тим Раугарден в курсе Алгоритмы 2 учит следующему подходу для обновления смежных вершин в куче min (после извлечения min из кучи):

When a vertice v is added to the MST:
  For each edge (v,w) in the unexplored tree:
      1. Delete w from the min heap.
      2. Recompute the key[w] (i.e. it's value from the unexplored tree
         to the explored one).
      3. Add the value back to the heap.

Таким образом, в основном это включает удаление из кучи (и heapify, которая занимает O (logn)), а затем повторную вставку (снова O (logn))

Вместо этого, если я использую следующий подход:

For each edge (v,w) in the unexplored tree:
    1. Get the position of the node in the heap(array) using HashMap -> O(1)
    2. Update the value in place.
    3. Bubble up or bubble down accordingly. -> O(logn)

Хотя они асимптотически одинаковы, последний дает лучшие константы. Так это лучше, чем в курсе? Или я что-то упустил?

Answer 1

Это асимптотически то же самое, и вы получите лучший постоянный коэффициент с высокой вероятностью. То, что вы пытаетесь достичь с помощью HashMap, использует O(n) дополнительного пространства. Кроме того, в худшем случае это займет O(logn) дополнительное время, так же, как будет стоить удаление из кучи. Однако вероятность того, что время будет пропорционально logn, действительно мала. Вы можете взглянуть на вероятностный анализ производительности конкретной реализации HashMap, которую вы намереваетесь использовать. если вы хотите узнать больше об этом.

Я мог бы предложить лучшее решение, которое избегает использования HashMap и, следовательно, легче наблюдать / анализировать постоянный коэффициент, поскольку не требует вероятностного анализа.

Решением является сохранение значений ключей во внешнем массиве A и переопределение функции сравнения кучи, чтобы она сравнивала элементы внутри нее на основе их соответствующих значений, которые хранятся в A.

Другими словами, функция сравнения по умолчанию во многих реализациях кучи выглядит следующим образом.

function compare(a, b):
    return a < b

При обновлении вы измените его на:

function compare(a, b):
    return A[a] < A[b]

В массиве A каждая вершина v будет иметь соответствующую ячейку, что приведет к O(n) дополнительному использованию пространства, как и ваша идея HashMap. Но обновление этого значения при добавлении v к обнаруженным узлам займет время O(1) даже в худшем случае.

Это обновление может быть невозможным на основе языка программирования, который вы реализуете, и библиотек, которые вы используете для кучи, но это возможно на многих языках и языках, включая, но не ограничиваясь, std:: priority_queue в C++ STL. Вы также можете реализовать это с помощью пользовательской реализации кучи, если вы ищете эксперимент с такой пользовательской структурой данных.