Как я могу использовать двоичную кучу в алгоритме Дейкстры?
Я пишу код алгоритма dijkstra, для части, где мы должны найти узел с минимальным расстоянием от используемого в данный момент узла, я использую массив и перебираю его полностью, чтобы вычислить узел.
Эта часть может быть заменена двоичной кучей, и мы можем вычислить узел за O (1) времени, но мы также обновим расстояние узла в дальнейших итерациях. Как я включу эту кучу?
В случае массива все, что мне нужно сделать, это перейти к индексу (ith -1) и обновить значение этого узла, но то же самое нельзя сделать в двоичной куче, мне придется выполнить полный поиск, чтобы вычислить из позиции узла, а затем обновить его.
Как обойти эту проблему?