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

Question

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

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) 

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

Answer 1

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

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

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

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

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

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

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

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

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