Алгоритм Прима с Трепами

Question

Может ли алгоритм Прима быть реализован с помощью трэпов, чтобы ускорить выполнение, потому что нормальная куча создаст проблему при обновлении значения ключей при сохранении вершин в кучах, что в противном случае потребовало бы пространства O(V) для хранения расположения вершин в куче?

Answer 1

Это не обязательно сделает алгоритм Прима быстрее. Рассмотрим следующий вырожденный случай - у вас есть n узлов v1, v2, ..., vn, и их приоритеты таковы, что p(v1)

Извините за отрицательный результат, но я надеюсь, что это поможет!