Фибоначчиева куча

Фибоначчиева куча — это структура данных, представляющая собой набор деревьев, удовлетворяющих свойству кучи (min-heap или max-heap), и поддерживающая операции с амортизированно низкой временной сложностью. Разработана Майклом Фредманом и Робертом Тарьяном в 1984 году. Название происходит от чисел Фибоначчи, которые используются в анализе амортизированной сложности операций. Фибоначчиева куча позволяет выполнять такие операции, как вставка, объединение (merge) и уменьшение ключа (decrease-key), за константное амортизированное время, а удаление минимального элемента — за логарифмическое. Эта структура данных применяется в алгоритмах, где требуется частое уменьшение ключей, например, в алгоритме Дейкстры для поиска кратчайших путей.

История

Фибоначчиева куча была предложена в 1984 году Майклом Фредманом и Робертом Тарьяном в статье «Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms». Разработка была мотивирована необходимостью улучшить производительность алгоритмов, работающих с графами, таких как алгоритм Дейкстры и алгоритм Прима. До появления фибоначчиевой кучи для этих задач использовались бинарные кучи, которые имели логарифмическую сложность для операций вставки и удаления минимума, но не поддерживали эффективное уменьшение ключа. Фибоначчиева куча позволила снизить амортизированную сложность операции уменьшения ключа до O(1), что дало существенное ускорение для алгоритмов с большим количеством таких операций.

Основные свойства

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

• ключ (key)
• указатель на родителя (parent)
• указатель на одного из детей (child)
• указатели на левого и правого брата (left, right) — для циклического двусвязного списка
• степень (degree) — количество детей узла
• флаг mark (отметка) — используется для управления структурой при уменьшении ключа

Свойство кучи

Для любого узла выполняется: ключ узла ≤ ключи всех его детей (для min-heap). Это свойство гарантирует, что минимальный элемент кучи всегда находится в корневом списке.

Амортизированный анализ

Амортизированная сложность операций в фибоначчиевой куче достигается за счёт использования «отложенной» работы. Операции, такие как вставка и объединение, выполняются быстро (O(1)), но могут создавать «мусор» в виде множества деревьев. Этот мусор убирается при выполнении операции удаления минимального элемента, которая включает фазу консолидации, где деревья с одинаковой степенью объединяются. Анализ использует потенциальную функцию, основанную на количестве деревьев и количестве помеченных узлов.

Операции

Вставка (insert)

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

Получение минимума (minimum)

Возвращается указатель на минимальный элемент, хранящийся в куче. Сложность: O(1).

Объединение куч (merge)

Два корневых списка объединяются в один, и выбирается новый минимум. Амортизированная сложность: O(1).

Удаление минимума (extract-min)

Это самая сложная операция. Она включает несколько шагов:

1. Удалить узел с минимальным ключом из корневого списка.
2. Добавить всех его детей в корневой список.
3. Выполнить консолидацию: объединить деревья с одинаковой степенью, чтобы уменьшить количество деревьев в корневом списке. Для этого используется массив указателей на корни, индексированный по степени. При консолидации два дерева одинаковой степени объединяются так, что корень с большим ключом становится ребёнком корня с меньшим ключом.
4. Обновить указатель на новый минимум.

Амортизированная сложность: O(log n), где n — количество элементов в куче.

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

Эта операция является ключевым преимуществом фибоначчиевой кучи. Если новый ключ меньше старого, то:

1. Узел отрезается от своего родителя и добавляется в корневой список.
2. Если родительский узел был помечен (mark = true), то он также отрезается и добавляется в корневой список, и процесс продолжается рекурсивно (каскадное отсечение).
3. Если родитель не был помечен, он помечается (mark = true).

Амортизированная сложность: O(1).

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

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

Применение

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

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

Преимущества и недостатки

Преимущества

• Амортизированно константное время для вставки, объединения и уменьшения ключа.
• Эффективность в алгоритмах с большим количеством операций уменьшения ключа.

Недостатки

• Высокая константа в реальном времени из-за сложности реализации и накладных расходов на поддержание структуры.
• Сложность реализации по сравнению с бинарными или биномиальными кучами.
• Не подходит для систем с жёсткими требованиями к реальному времени, так как амортизированная сложность может приводить к редким, но длительным операциям (например, при консолидации).

Реализация

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

Сравнение с другими кучами

• — амортизированная сложность.

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

• Название «Фибоначчиева куча» связано с тем, что в анализе амортизированной сложности используются числа Фибоначчи. В частности, доказывается, что размер поддерева с корнем степени k не меньше числа Фибоначчи F_{k+2}.
• Фибоначчиева куча не является самой быстрой на практике для большинства задач из-за высоких накладных расходов. Для многих приложений предпочтительнее использовать бинарные кучи или более простые структуры, такие как кучи с косой (skew heap) или парные кучи (pairing heap).
• В 2012 году была предложена улучшенная версия — «куча с ленивым удалением» (lazy heap), которая упрощает реализацию.

Источники

• 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.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2005). Алгоритмы: построение и анализ. 2-е издание. М.: Вильямс.
• Sedgewick, R., & Wayne, K. (2011). Algorithms. 4th edition. Addison-Wesley.