Быстрое обновление ключей внутри кучи в алгоритме Дейкстры

#алгоритм #haskell

Хочется с нуля реализовать алгоритм Дейкстры на Haskell. Для этого я написал двоичную
кучу на дереве.

При написании самого алгоритма возникла проблема: необходимо для соседей данной вершины
обновлять ключи внутри кучи.

Каким образом можно на функциональном языке это достаточно быстро сделать, не просматривая
всю кучу?
    

Ответы

Ответ 1

Нужна структура поддерживающая следующее:


добавление нового значения за O(logN)
узнать минимальный элемент за O(1)
удалить минимальный элемент за O(logN)
изменить значение элемента за O(logN)


Будем хранить кроме стандартной кучи, массив valueToIndex[v] = index , в котором
для каждой вершины v, храниться указатель/индекс на элемент в куче, где храниться значение
времени для этой вершины.

Когда требуется изменить значение в какой то вершине:


получаем ссылку на элемент в куче, используя массив valueToIndex
изменяем значение 
т.к. для дейкстры значение может только
уменьшится, то необходимо пропихнуть вверх данный элемент по
рекурсии (не более logN подъемов)


Так же во всех стандартных функциях кучи, при изменении расположения элементов необходимо
обновлять значения массива valueToIndex[].

Если реализовывать кучу не на массивах, то необходимо хранить ссылку на предка.

Если какой то момент не понятен, то распишу подробней.