Изменения

Перейти к: навигация, поиск

Алгоритм Прима

1079 байт убрано, 13:42, 12 октября 2014
Реализация
Q.decreaseKey(u, key[u])
Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.<br>Сделать операцию <tex>decreaseKey</tex> для приоритетной очереди на [[Двоичная_куча | двоичной куче]] немного проблематично, поэтому есть два варианта. Первый, написать приоритетную очередь на какой-то сложной куче, например, [[Биномиальная_куча | биноминальной]]. Второй, изменять значение ключа вершины, для которой вызвали <tex>decreaseKey</tex>, напрямую в массиве, в котором хранится куча, после чего делать процедуру просеивания вверх для этой вершины. Для быстрого доступа к позиции вершины в массиве, нужно дополнительно хранить указатель на эту позицию и не забывать его менять во время изменения кучи.
==Пример==
Анонимный участник

Навигация