Куча Фибоначчи

Куча Фибоначчи — это структура данных, реализующая абстрактный тип данных «очередь с приоритетом», представляющая собой набор деревьев, удовлетворяющих свойству неубывающей пирамиды (heap property). Куча Фибоначчи отличается от других типов куч (например, бинарной или биномиальной) тем, что большинство операций, включая вставку, слияние и уменьшение ключа, выполняются за амортизированное константное время O(1), а операция извлечения минимального элемента — за амортизированное O(log n), где n — количество элементов в куче. Структура была разработана в 1984 году Майклом Фредманом и Робертом Тарьяном и получила своё название из-за использования чисел Фибоначчи в анализе амортизационной сложности.

История

Куча Фибоначчи была впервые описана в 1984 году в совместной работе Майкла Фредмана и Роберта Тарьяна «Fibonacci heaps and their uses in improved network optimization algorithms» (опубликована в журнале Journal of the ACM). Разработка структуры была мотивирована необходимостью ускорить алгоритмы на графах, такие как алгоритм Дейкстры для поиска кратчайших путей и алгоритм Прима для построения минимального остовного дерева. В этих алгоритмах ключевой операцией является уменьшение ключа (decrease-key), которая в бинарных кучах выполняется за O(log n). Куча Фибоначчи позволила выполнять эту операцию за амортизированное O(1), что дало значительный выигрыш в асимптотике для разреженных графов.

Структура и свойства

Куча Фибоначчи представляет собой набор (лес) корневых деревьев, каждое из которых является пирамидой (min-heap). Это означает, что ключ любого узла не больше ключей его дочерних узлов. В отличие от биномиальной кучи, деревья в куче Фибоначчи не обязаны быть биномиальными, и их степени (количество дочерних узлов) не ограничены строго. Куча хранит следующие данные:

• Указатель на корневой узел с минимальным ключом (min).
• Счётчик общего количества узлов (n).
• Для каждого узла: указатели на родителя, на одного из дочерних узлов, на левого и правого брата (циклический двусвязный список), а также флаг «потерянный ребёнок» (mark) и степень (количество дочерних узлов).

Свойство «потерянного ребёнка»

Ключевая особенность, обеспечивающая амортизационную эффективность, — это правило, ограничивающее количество дочерних узлов у каждого узла. Если узел теряет второго ребёнка (то есть из него вырезают два дочерних узла), он сам отрезается от своего родителя и перемещается в корневой список. Это гарантирует, что степень любого узла не превышает O(log n), что критично для анализа сложности.

Операции

Вставка (insert)

Новый элемент добавляется в корневой список как отдельное дерево. Если его ключ меньше текущего минимального, указатель min обновляется. Амортизированное время — O(1).

Слияние (merge)

Две кучи Фибоначчи объединяются путём конкатенации их корневых списков и обновления указателя на минимальный элемент. Амортизированное время — O(1).

Получение минимального элемента (find-min)

Возвращает узел, на который указывает min. Амортизированное время — O(1).

Извлечение минимального элемента (extract-min)

Наиболее сложная операция. Сначала минимальный узел удаляется, а все его дочерние узлы перемещаются в корневой список. Затем выполняется процедура консолидации (consolidate): в массиве размером O(log n) подсчитываются корневые узлы одинаковой степени, и они попарно связываются (узел с большим ключом становится дочерним узла с меньшим ключом), пока все корни не будут иметь различные степени. Амортизированное время — O(log n).

Уменьшение ключа (decrease-key)

Ключ узла уменьшается до нового значения. Если это нарушает свойство пирамиды (новый ключ меньше ключа родителя), узел вырезается из своего родителя и перемещается в корневой список. Если родитель уже был помечен (mark = true), то он также вырезается, и процесс рекурсивно продолжается вверх по дереву (каскадное вырезание). Амортизированное время — O(1).

Удаление узла (delete)

Удаление узла реализуется путём уменьшения его ключа до минус бесконечности (или до значения, меньшего всех остальных) с последующим извлечением минимального элемента. Амортизированное время — O(log n).

Анализ сложности

Амортизационный анализ кучи Фибоначчи использует метод потенциалов. Потенциальная функция определяется как Φ = (количество корней) + 2 * (количество помеченных узлов). Каждая операция вставки увеличивает количество корней на 1, что увеличивает потенциал на 1, и её амортизированная стоимость составляет O(1). Операция уменьшения ключа может вызвать каскадное вырезание, которое уменьшает потенциал, компенсируя затраты на рекурсивные вырезы.

Асимптотическая сложность операций:

Применение

Куча Фибоначчи используется в алгоритмах, где требуется большое количество операций уменьшения ключа, особенно на разреженных графах:

• Алгоритм Дейкстры: для поиска кратчайших путей от одной вершины. Использование кучи Фибоначчи снижает асимптотическую сложность с O((V+E) log V) до O(V log V + E), где V — количество вершин, E — количество рёбер.
• Алгоритм Прима: для построения минимального остовного дерева. Аналогично, сложность снижается до O(E + V log V).
• Другие алгоритмы на графах: алгоритм Джонсона для разреженных графов, некоторые задачи потоковой оптимизации.

Недостатки

Несмотря на теоретически привлекательную асимптотику, куча Фибоначчи редко используется на практике по следующим причинам:

• Высокие константы: реализация требует сложного управления указателями и поддержания двусвязных списков, что приводит к большим накладным расходам памяти и времени выполнения для реальных данных.
• Сложность реализации: код кучи Фибоначчи значительно сложнее, чем код бинарной или биномиальной кучи, что увеличивает вероятность ошибок.
• Практическая эффективность: для большинства прикладных задач, особенно с небольшими размерами данных, бинарная куча или куча с прямым адресованием (например, в алгоритме Дейкстры для графов с малым весом рёбер) оказываются быстрее.
• Плохая производительность на практике: из-за большого количества операций с памятью (выделение/освобождение узлов, перестановка указателей) куча Фибоначчи часто проигрывает более простым структурам, таким как куча Бродала (Brodal queue) или куча с парами (pairing heap), которые также имеют хорошую асимптотику, но проще в реализации.

Интересные факты

• Название «Фибоначчи» связано с тем, что в амортизационном анализе используется свойство чисел Фибоначчи: степень любого узла не превышает числа Фибоначчи с номером, равным размеру поддерева.
• Роберт Тарьян, один из создателей структуры, является лауреатом премии Тьюринга (1986) за вклад в теорию алгоритмов и структур данных.
• Куча Фибоначчи была одной из первых структур данных, для которой был применён метод амортизационного анализа с использованием потенциалов.

Источники

• Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3), 596–615.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2013). Алгоритмы: построение и анализ (3-е изд.). М.: Вильямс. — Глава 19: «Кучи Фибоначчи».
• Седжвик, Р., Уэйн, К. (2016). Алгоритмы на Java (4-е изд.). М.: Вильямс. — Глава 6: «Очереди с приоритетом».