Куча Фибоначчи: ленивая структура и амортизация

Куча Фибоначчи - это «ленивая» mergeable-приоритетная очередь, предложенная Майклом Фредманом и Робертом Тарьяном в 1984 году. Её главная особенность - амортизированные оценки: insert, find-min, merge и decrease-key работают за $O(1)$, а extract-min и delete - за $O(\log n)$ amortized. Имя «Фибоначчи» возникло не из-за вспомогательных счётчиков, а из доказательства верхней границы степени узла: размер поддерева, висящего у узла степени $d$, ограничен снизу числом Фибоначчи $F_{d+2}$, откуда $D(n) \le \log_\varphi n$.

Идея: откладываем работу до последнего момента

В биномиальной куче после каждого insert приходится поддерживать инвариант «уникальные ранги в лесу». Это даёт $O(\log n)$ worst-case на вставку. Куча Фибоначчи действует ровно наоборот: insert просто добавляет новый одноузловой корень в общий двусвязный корневой список и обновляет указатель на минимум. Никаких сливаний. Структура временно становится «грязной» - деревьев одного ранга может быть сколько угодно.

Очистка (консолидация) откладывается до ближайшего extract-min. Только тогда алгоритм просматривает все корни, последовательно объединяет деревья одинаковой степени, пока в лесу не останется не более одного дерева каждой степени. Эта работа единовременно дорогая, но её стоимость размазывается на дешёвые insert и decrease-key - отсюда амортизированные $O(1)$.

Чем куча Фибоначчи отличается от биномиальной

Биномиальная куча - это лес строгих биномиальных деревьев $B_k$, и каждое слияние выполняется немедленно. Куча Фибоначчи отказывается от строгой формы деревьев: после серии decrease-key дерево может потерять детей и стать «обрезанным», не сохраняя $2^k$ узлов на ранг $k$. Зато все «ленивые» правки выполняются за константу, а реальная стоимость возникает только при extract-min.

Структура данных и пометки

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

Флаг mark ставится, когда у узла потеряли первого ребёнка (через decrease-key, который вырезал ребёнка в корневой список). При потере второго ребёнка узел сам становится корнем - это и есть каскадный cut. Такая дисциплина гарантирует, что дерево не «разваливается» произвольно и сохраняет нижнюю оценку размера через числа Фибоначчи.

Операции и их амортизированная стоимость

• insert(x): создать одноузловое дерево, добавить в root list, при необходимости обновить min. Амортизированно $O(1)$, реальное время - тоже $O(1)$.
• find-min: вернуть min. $O(1)$ - указатель поддерживается актуальным.
• merge(H1, H2): склеить два двусвязных кольца корней и взять минимум из двух min-указателей. $O(1)$.
• extract-min: удалить корневой узел, всех его детей перенести в root list, затем выполнить консолидацию. Амортизированно $O(\log n)$.
• decrease-key(v, k'): уменьшить ключ. Если heap-order не нарушен - конец. Иначе вырезать $v$ из родителя в root list, снять mark у $v$, и при необходимости запустить каскадный cut вверх. Амортизированно $O(1)$.
• delete(v): decrease-key(v, -\infty) + extract-min. $O(\log n)$ amort.

Консолидация при extract-min

После удаления min его дети попадают в root list. Затем алгоритм заводит массив A размера примерно $D(n) + 1$, индексированный по степени узла, и идёт по корневому списку. Для каждого корня $r$ степени $d$: если A[d] пуст - кладём $r$ туда; если занят - сливаем $r$ с A[d] (меньший ключ становится корнем), степень итога $d+1$, и пробуем уложить уже его (рекурсивно). В конце по A строится новый root list и обновляется min.

Время фактической работы - $O(\#\text{root list} + D(n))$, но поскольку корней до консолидации могло быть много (после ленивых insert'ов), реальная стоимость может быть линейна. Амортизация делает оценку $O(\log n)$ - за счёт того, что предыдущие insert-ы добавили потенциал.

Каскадный cut и правило mark

decrease-key имеет красивую дисциплину «mark-and-cut». Когда у узла $x$ вырезают одного ребёнка decrease-key'ем (а сам $x$ не корень), на $x$ ставится флаг mark. Если $x$ потом теряет ещё одного ребёнка - он сам вырезается в root list, его mark снимается, и проверка переходит на родителя $x$. Так каскад поднимается по дереву, пока не встретит немаркированный узел или корень. На длинной серии cut'ов работа реальная немалая, но каждый cut уменьшает потенциал, и амортизированный счёт остаётся $O(1)$ на одну decrease-key.

Правило гарантирует, что узел теряет не более одного ребёнка между двумя моментами, когда сам становится ребёнком. Это и есть структурный инвариант, на котором строится оценка через $F_{d+2}$.

Потенциальная функция и почему $\varphi$

Анализ амортизации использует функцию

$$\Phi(H) = t(H) + 2\,m(H),$$

где $t(H)$ - число деревьев в root list, $m(H)$ - число помеченных узлов. insert увеличивает $\Phi$ на 1 (один новый корень), потому амортизированная цена $1 + 1 = O(1)$. extract-min уменьшает $\Phi$ на $t(H) - D(n) - 1$ (конечное число деревьев $\le D(n)+1$), компенсируя реальное время. decrease-key тратит $1$ на самого себя плюс по $1$ на каждый каскадный cut, но каждый cut снимает mark и уменьшает $\Phi$ на $2$ - и amortized cost схлопывается до $O(1)$.

Граница $D(n) \le \log_\varphi n$ выводится так: пусть $S_d$ - минимальный размер поддерева, корень которого имеет степень $d$. Из инвариантов получаем $S_d \ge F_{d+2}$, где $F_k$ - числа Фибоначчи. Поскольку $F_{d+2} \ge \varphi^d$ ($\varphi = (1+\sqrt 5)/2$), имеем $n \ge \varphi^d$, откуда $d \le \log_\varphi n$.

Применение: Дейкстра на разреженных графах

Алгоритм Дейкстры с бинарной кучей даёт $O((|E| + |V|)\log |V|)$, потому что decrease-key стоит $O(\log V)$ и вызывается до $|E|$ раз. Замена кучи на Фибоначчиеву превращает оценку в

$$O(|E| + |V|\log |V|).$$

На плотных графах ($|E| = \Theta(V^2)$) это уже $O(V^2)$ против $O(V^2 \log V)$ - реальное ускорение. Та же асимптотика всплывает в алгоритме Прима для MST и в ряде задач сетевого потока (например, $O(VE + V^2 \log V)$ Galil-Tardos для min-cost flow). На разреженных графах разница меньше, и из-за больших констант на практике часто оставляют бинарную или $d$-арную кучу - теоретическая оптимальность куч Фибоначчи редко окупается в коде на C++.

Частые ошибки

• Думают, что Фибоначчи-куча быстрее во всех случаях. На малых $n$ и без массовых decrease-key бинарная куча на массиве почти всегда выигрывает по константам и cache locality.
• Забывают про каскадный cut. Без него амортизированная оценка decrease-key ломается, и в худшем случае операция станет линейной. Mark - не косметика, а часть доказательства.
• Путают $D(n)$ и высоту дерева. $D(n)$ - это верхняя оценка степени корня, а не высоты; высота может быть больше из-за длинных «цепочек» после серии cut'ов.
• Считают, что extract-min - $O(\log n)$ worst-case. Нет, только amortized. Один extract-min после миллиона insert'ов реально пройдёт по миллиону корней - амортизация распределит стоимость на предыдущие операции.
• Игнорируют размер константы. В научных бенчмарках куча Фибоначчи проигрывает $d$-арной и парной (pairing) куче почти всегда - она нужна как теоретический инструмент.

FAQ

Почему именно «Фибоначчи»? Потому что минимальный размер поддерева с корнем степени $d$ ограничен снизу числом $F_{d+2}$. Это даёт $D(n) \le \log_\varphi n$ и обеспечивает $O(\log n)$ amortized на extract-min.

В чём принципиальная разница с биномиальной кучей? Биномиальная куча поддерживает строгие $B_k$ и платит за insert и merge сразу. Куча Фибоначчи откладывает работу до extract-min, разрешает временно несбалансированные деревья и компенсирует это каскадным cut с mark.

Когда стоит реализовывать куча Фибоначчи в продакшене? Почти никогда. Её используют там, где нужно гарантированное $O(E + V\log V)$ для Дейкстры на плотных графах в теоретических работах. На практике предпочитают парные или $d$-арные кучи - у них схожая асимптотика с лучшими константами.

Коротко

Куча Фибоначчи - ленивая mergeable-куча: insert, decrease-key и merge за амортизированное $O(1)$, extract-min и delete за $O(\log n)$ amortized. Грязный root list очищается только при extract-min (консолидация), а правило mark-and-cut с каскадным вырезанием держит структуру деревьев в рамках $D(n) \le \log_\varphi n$. На алгоритме Дейкстры это даёт $O(E + V\log V)$ против $O((E+V)\log V)$ на бинарной куче - теоретическая победа, на практике перекрываемая константами.