Фибоначчиева куча: Секретное оружие алгоритма Дейкстры
Когда мы обсуждали алгоритм Дейкстры для поиска кратчайшего пути, мы упомянули, что он использует приоритетную очередь для извлечения вершины с минимальным расстоянием. Если использовать обычный массив, извлечение минимума займет время O(V). Если использовать классическую Бинарную кучу (Binary Heap), время извлечения и время обновления (уменьшения) ключа составят O(log V). Для разреженных графов это отлично. Но для очень плотных графов, где количество ребер огромно и операция "Уменьшить ключ" (Decrease-Key) вызывается миллионы раз, логарифм начинает тормозить систему. В 1984 году Майкл Фредман и Роберт Тарьян создали Фибоначчиеву кучу, чтобы преодолеть этот барьер.
Фибоначчиева куча (Fibonacci Heap) — это потрясающе сложная структура данных, представляющая собой не одно дерево, а целый лес (набор) независимых деревьев (heap-ordered trees). Эти деревья не обязаны быть идеально сбалансированными бинарными деревьями; их узлы могут иметь любое количество потомков.
Секрет непревзойденной скорости этой структуры кроется в ленивых вычислениях (Lazy Evaluation). Когда мы вставляем новый элемент в кучу или уменьшаем значение ключа, классическая бинарная куча начинает судорожно "всплывать" или "тонуть" элемент, балансируя структуру (на что тратится O(log N) времени). Фибоначчиева куча этого не делает! Она просто отрезает измененный узел и бросает его в корневой список (связный список корней нашего леса деревьев), обновляя указатель на минимум.
Благодаря этой лени: операции Insert, Find-Min, Merge (слияние двух куч) и самое главное Decrease-Key выполняются за амортизированное время O(1) (то есть практически мгновенно, за несколько тактов процессора).
Вся тяжелая работа откладывается "на потом" и выполняется только во время одной единственной операции — Extract-Min (удаление минимума). В этот момент куча проводит генеральную уборку (консолидацию): она объединяет деревья с одинаковыми степенями ветвления (количеством детей), пока все деревья в лесу не станут иметь разные степени. Математический анализ Тарьяна показал, что максимальная степень любого дерева в такой куче ограничена числом O(log N), а размеры деревьев растут в точности по закону чисел Фибоначчи (отсюда и название структуры!).
Использование Фибоначчиевой кучи позволяет снизить теоретическую асимптотическую сложность алгоритма Дейкстры с O(E log V) до O(E + V log V). Для плотных графов (где количество ребер E близко к V^2) это дает колоссальный математический прирост производительности. Этот же подход ускоряет алгоритм Прима для поиска минимального остовного дерева.
