Реализация алгоритма Дейкстры с использованием STL make_heap

Question

Как минимум пара ответов рекомендует использовать функции кучи STL для реализации очереди приоритетов в алгоритме Дейкстры:

Производительность реализации алгоритма Дейкстры

Реализация алгоритма Дейкстры

Каков наилучший способ переупорядочить вершины в куче ( строка 19 ), учитывая, что STL не включает функцию кучи для обновления ключей?

Answer 1

Вам нужно позволить вершине «пузыриться» через кучу (при необходимости заменяя ее своим родителем), пока она не достигнет своей новой позиции в куче.

В псевдо-C ++ адаптирован из Введение в алгоритмы 2-е изд.стр.140:

heap[pos] = new_weight;
while (pos > 0 && heap[parent(pos)] > heap[pos]) {
    swap(heap[parent(pos)], heap[pos]);
    pos = parent(pos);
}

, где int parent(int pos) { return (pos-1)/2; }

Answer 2

Я думаю, есть несколько способов сделать это.

Вы можете вручную выполнить операцию sift-up и, в основном, перенести значение в верхнюю часть кучи, вытолкнуть его и затем задвинуть обратно в кучу с новым значением.

Вы можете обновить значение и снова выполнить make_heap в куче, предполагая, что make_heap разработан, чтобы быть эффективным, когда куча уже "почти куча".

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

В противном случае вы можете использовать другую реализацию кучи, которая имеет функциональность обновления. Например, библиотека Boost.Graph включает в свои подробности (папка boost / graph / detail) заголовок d_ary_heap.hpp, который реализует реализацию D-Ary Heap Indirect, которая имеет функцию обновления logN. Это используется в реализации Dijkstra и A * в BGL, которую вы также можете использовать напрямую вместо реализации своей собственной.