Как обновить приоритеты элементов в куче для алгоритма Прима?
Я изучаю алгоритм Прима. В коде есть часть, следующая вершина которой будет проходить через множество вершин, принадлежащихMST
, При этом мы также должны «обновить все вершины в другом наборе, которые смежны с уходящей вершиной». Это снимок сCLRS
:
Интересная часть лежит в строке №. 11. Но так как мы используем кучу здесь, у нас есть доступ только к минимальному элементу, верно (heap[0]
)? Итак, как мы можем искать и обновлять вершины из кучи, даже если они не являются минимальными, и, таким образом, мы знаем, где они находятся, кроме как с помощью линейного поиска?