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

TL;DR

Фибоначчиева куча (Fibonacci heap) — очередь с приоритетом из набора деревьев, связанных в циклические двусвязные списки, с амортизированными оценками лучше, чем у двоичной и биномиальной куч: вставка и слияние за [math]\displaystyle{ O(1) }[/math], а уменьшение ключа — за амортизированное [math]\displaystyle{ O(1) }[/math]. За это платит извлечение минимума — амортизированное [math]\displaystyle{ O(\log n) }[/math]. Такие границы ускоряют алгоритм Дейкстры до [math]\displaystyle{ O(m + n\log n) }[/math] и дают лучшие теоретические оценки для задач на графах. Цена — сложная реализация (циклические списки, метки, каскадные отсечения) и большие константы, из-за чего на практике её часто обгоняют двоичная и pairing-кучи. Структуру предложили М. Фредман и Р. Тарджан в 1984–1987 гг.

Свойство	Значение
Класс	Лес кучеобразных деревьев в циклических списках; очередь с приоритетом
Изобретение	М. Фредман и Р. Тарджан, 1984 (FOCS), 1987 (JACM) [2][3]
Insert	[math]\displaystyle{ O(1) }[/math] (амортизированно)
Find-Min	[math]\displaystyle{ O(1) }[/math]
Union / Merge	[math]\displaystyle{ O(1) }[/math] (амортизированно)
Extract-Min	амортизированно [math]\displaystyle{ O(\log n) }[/math]
Decrease-Key	амортизированно [math]\displaystyle{ O(1) }[/math]
Delete	амортизированно [math]\displaystyle{ O(\log n) }[/math]
Память	[math]\displaystyle{ O(n) }[/math]; на узел — key, degree, mark, parent, child, left, right
Упорядоченность	Частичная: каждое дерево — min-куча; минимум в min
Стабильность	Неприменима
Альтернативы	Двоичная куча, биномиальная куча, pairing-куча, rank-pairing куча, очередь Бродала
Где встречается	алгоритм Дейкстры и Прима, сетевая оптимизация, Boost.Heap (fibonacci_heap), теоретические оценки MST

Определения

Фибоначчиева куча (Fibonacci heap) — набор (лес) деревьев, каждое из которых подчиняется свойству кучи (ключ узла не больше ключей детей), а корни связаны в циклический двусвязный список. Каждый узел хранит:

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

Метка (mark). Узел помечен, если он стал ребёнком и с тех пор потерял ровно одного ребёнка; при потере второго его самого вырезают в корни. Корни не помечаются. Метка — это «счётчик потерянных детей», сжатый до одного бита.

Форма деревьев не фиксирована: допускаются любые кучеобразные деревья (в отличие от строго биномиальных). Ограничитель формы — правило меток, из которого вытекает [math]\displaystyle{ O(\log n) }[/math] на степень узла.

Потенциал (potential). Для амортизационного анализа вводится

[math]\displaystyle{ \Phi(H) = t(H) + 2\,m(H), }[/math]

где [math]\displaystyle{ t(H) }[/math] — число деревьев в списке корней, [math]\displaystyle{ m(H) }[/math] — число помеченных узлов.

Обозначения. [math]\displaystyle{ n }[/math] — число элементов, [math]\displaystyle{ m(H) }[/math] — число помеченных узлов (в потенциале); [math]\displaystyle{ m }[/math] без аргумента — число рёбер графа (в применениях), [math]\displaystyle{ \log }[/math] — по основанию 2, [math]\displaystyle{ \varphi = (1+\sqrt5)/2 \approx 1.618 }[/math] — золотое сечение, [math]\displaystyle{ D(n) }[/math] — максимальная степень узла. NIL — пустая ссылка.

Рис. 1. Корни связаны в циклический список, дети каждого узла — тоже циклический список. Пунктирным кольцом отмечены помеченные узлы (потеряли одного ребёнка).

Мотивация и интуиция

Двоичная и биномиальная кучи делают decrease-key за [math]\displaystyle{ O(\log n) }[/math]. Именно на нём «спотыкаются» графовые алгоритмы: в Дейкстре при релаксации ребра нужно уменьшить оценку расстояния вершины, и такое уменьшение выполняется до [math]\displaystyle{ m }[/math] раз. Итоговая стоимость — [math]\displaystyle{ O(m\log n) }[/math]. Если бы decrease-key был константным, стало бы [math]\displaystyle{ O(m + n\log n) }[/math] — заметно лучше на разреженных графах.

Почему вообще [math]\displaystyle{ O(\log n) }[/math]? Потому что при уменьшении ключа приходится восстанавливать строгую форму дерева. Фибоначчиева куча отказывается от этого: она откладывает работу. Узел с уменьшенным ключом просто вырезается из родителя и бросается в список корней — за [math]\displaystyle{ O(1) }[/math]. Деревья при этом «рассыпаются», но за них никто не платит в момент отсечения.

Чтобы не дать куче окончательно рассыпаться, вводится правило: узел можно вырезать не более однажды, пока он сам не стал корнем. За это следит метка. Если узел теряет второго ребёнка, его самого вырезают в корни — и так «каскадом» вверх. Именно это правило, вместе с метками и потенциалом [math]\displaystyle{ \Phi(H) = t(H) + 2m(H) }[/math], доказывает, что суммарная стоимость отсечений линейна по числу операций. А редкая дорогая операция Extract-Min «консолидирует» накопившиеся деревья, приводя список корней в порядок.

Идея в одной фразе: дешёвые операции копят беспорядок, а дорогие — разбирают его; амортизация показывает, что в среднем всё дёшево.

Устройство

Фибоначчиева куча состоит из трёх слоёв (см. рис. 1):

• Деревья — кучеобразные (min-heap), произвольной формы.
• Циклические списки. Корни образуют циклический двусвязный список; дети каждого узла — тоже циклический список. Цикличность позволяет за [math]\displaystyle{ O(1) }[/math] сцепить два списка (слияние куч) и вставить узел, не храня длину.
• Указатель min — один из корней с минимальным ключом. Минимум доступен за [math]\displaystyle{ O(1) }[/math].

Особенности, отличающие структуру от биномиальной:

• Деревья не обязаны быть биномиальными: степень узла может быть любой, лишь бы выполнялось правило меток.
• degree[u] — число детей; при Link оно растёт, при Cut — падает.
• Список корней может содержать много деревьев одинаковой степени — пока не выполнится Extract-Min.

Именно циклические списки и метки дают константные Insert, Union и Decrease-Key.

Операции и алгоритмы

Операция: слияние деревьев (Link)

Идея. Сделать корень [math]\displaystyle{ y }[/math] ребёнком корня [math]\displaystyle{ x }[/math] с меньшим ключом: два дерева превращаются в одно (рис. 2). Применяется при консолидации к корням равной степени.

Пошаговое описание.

1. Удалить [math]\displaystyle{ y }[/math] из списка корней.
2. Присоединить [math]\displaystyle{ y }[/math] к списку детей [math]\displaystyle{ x }[/math], задать parent[y] = x.
3. Увеличить degree[x], снять mark[y].

Инвариант. Дерево с корнем [math]\displaystyle{ x }[/math] остаётся кучеобразным; список корней не содержит [math]\displaystyle{ y }[/math].

Псевдокод.

Алгоритм Fibonacci-Heap-Link(H, y, x)
Вход:  x, y — корни; key[x] ≤ key[y]
Выход: y — ребёнок x; степень x увеличена
1  удалить y из списка корней H
2  parent[y] ← x
3  if child[x] = NIL
4      child[x] ← y
5  else
6      вставить y в циклический список детей x
7  degree[x] ← degree[x] + 1
8  mark[y] ← FALSE

Сложность: O(1) времени и памяти.
Корректность: key[x] ≤ key[y], поэтому свойство min-кучи сохраняется;
mark[y] снимается, так как y больше не потерявший ребёнка «ребёнок ребёнка».

Крайний случай. mark[y] снимается всегда: будучи ребёнком, узел начинает с нулём потерянных детей.

Рис. 2. Link(y, x): y покидает список корней и становится ребёнком x; degree(x) растёт, mark(y) снимается.

Операция: вставка (Insert)

Идея. Создать одноэлементное дерево и вставить его в список корней; при необходимости обновить минимум. Деревья не сливаются — работа откладывается до Extract-Min.

Пошаговое описание.

1. Инициализировать узел [math]\displaystyle{ x }[/math] (степень 0, без родителя и детей, mark = false).
2. Вставить [math]\displaystyle{ x }[/math] в циклический список корней.
3. Если ключ [math]\displaystyle{ x }[/math] меньше ключа min (или куча пуста) — обновить min.

Инвариант. Все свойства кучи и списков сохранены; добавлен ровно один элемент.

Псевдокод.

Алгоритм Fibonacci-Heap-Insert(H, x)
Вход:  H — фибоначчиева куча; x — новый узел с key[x]
Выход: H содержит x; min обновлён
1  degree[x] ← 0
2  parent[x] ← NIL
3  child[x] ← NIL
4  mark[x] ← FALSE
5  left[x] ← x
6  right[x] ← x
7  вставить x в список корней H
8  if min[H] = NIL or key[x] < key[min[H]]
9      min[H] ← x
10 n[H] ← n[H] + 1

Сложность: O(1) фактически и амортизированно (ΔΦ = +1).
Корректность: вставка лишнего корня не нарушает свойство min-кучи;
список корней остаётся циклическим, min при необходимости обновлён.

Крайний случай. Вставка в пустую кучу делает [math]\displaystyle{ x }[/math] единственным корнем и минимумом.

Операция: чтение минимума (Find-Min)

Идея. Минимум хранится в min[H], поэтому выдача — за [math]\displaystyle{ O(1) }[/math]: ни обхода деревьев, ни сравнений ключей не требуется.

Пошаговое описание.

1. Вернуть указатель min[H] (если куча пуста, он равен NIL).

Инвариант. min[H] указывает на корень с минимальным ключом во всём лесе — или равен NIL, когда элементов нет.

Псевдокод.

Алгоритм Fibonacci-Heap-Minimum(H)
Вход:  H — фибоначчиева куча
Выход: узел-минимум min[H] либо NIL, если куча пуста
Инвариант: min[H] — корень с наименьшим ключом

1  return min[H]

Сложность: O(1) фактически и амортизированно, O(1) памяти.
Корректность: указатель min[H] обновляют все операции, способные изменить минимум
(Insert, Union, Decrease-Key, Extract-Min), поэтому он всегда указывает на корень
с наименьшим ключом.

Разбор на примере. В куче на рис. 1 корни — 3, 8 и 14; min[H] указывает на 3, и операция возвращает его, не просматривая список корней.

Крайний случай. Пустая куча: min[H] = NIL, операция возвращает NIL; разыменовывать его нельзя, вызывающий код обязан проверить результат.

Операция: объединение куч (Union)

Идея. Сцепить два циклических списка корней за [math]\displaystyle{ O(1) }[/math] и выбрать меньший из двух минимумов.

Пошаговое описание.

1. Сцепить список корней [math]\displaystyle{ H_1 }[/math] со списком корней [math]\displaystyle{ H_2 }[/math].
2. min — меньший из min[H1], min[H2].
3. Сложить счётчики элементов.

Инвариант. Получен корректный лес, содержащий объединение элементов.

Псевдокод.

Алгоритм Fibonacci-Heap-Union(H1, H2)
Вход:  две фибоначчиевы кучи
Выход: куча со всеми элементами
1  H ← Make-Fib-Heap()
2  min[H] ← min[H1]
3  сцепить списки корней H1 и H2          # O(1), меняются только 4 указателя
4  if min[H1] = NIL or (min[H2] ≠ NIL and key[min[H2]] < key[min[H1]])
5      min[H] ← min[H2]
6  n[H] ← n[H1] + n[H2]
7  return H

Сложность: O(1) фактически и амортизированно.
Корректность: списки корней сцеплены без потери узлов, min[H] выбран как меньший из двух минимумов, счётчики сложены, поэтому результат — корректная куча со всеми элементами.

Крайний случай. Объединение с пустой кучей возвращает вторую без изменения списка.

Операция: уменьшение ключа (Decrease-Key), Cut и каскадное отсечение

Идея. Уменьшить ключ. Если он стал меньше ключа родителя, вырезать узел в список корней (это восстанавливает свойство кучи, потому что корень никому не подчинён). Затем запустить каскадное отсечение родителя по правилу меток.

Пошаговое описание.

1. Если новый ключ больше текущего — ошибка; иначе присвоить.
2. Если узел не корень и его ключ меньше ключа родителя — Cut, затем Cascading-Cut родителя.
3. Обновить min, если ключ стал меньше.

Инвариант. Свойство min-кучи восстановлено: узел либо корень, либо не меньше родителя; каждый узел теряет не более одного ребёнка, пока сам не станет корнем (гарантия меток).

Псевдокод.

Алгоритм Fibonacci-Heap-Decrease-Key(H, x, k)
Вход:  x — узел; k — новый ключ, k ≤ key[x]
Выход: key[x] = k; свойства кучи восстановлены
1  if k > key[x]
2      error "новый ключ больше текущего"
3  key[x] ← k
4  y ← parent[x]
5  if y ≠ NIL and key[x] < key[y]
6      Cut(H, x, y)
7      Cascading-Cut(H, y)
8  if key[x] < key[min[H]]
9      min[H] ← x

Алгоритм Cut(H, x, y)
Вход:  y — родитель x; x — ребёнок, который вырезается в корни
Выход: x — корень; degree[y] уменьшена, mark[x] снят
1  удалить x из списка детей y
2  degree[y] ← degree[y] − 1
3  вставить x в список корней H
4  parent[x] ← NIL
5  mark[x] ← FALSE

Алгоритм Cascading-Cut(H, y)
Вход:  y — узел, потерявший ребёнка
Выход: mark[y] выставлен либо y вырезан и каскад продолжен у его родителя
1  z ← parent[y]
2  if z ≠ NIL
3      if mark[y] = FALSE
4          mark[y] ← TRUE                # потерян первый ребёнок — только метка
5      else
6          Cut(H, y, z)                  # потерян второй ребёнок — вырезаем y
7          Cascading-Cut(H, z)           # и продолжаем вверх

Сложность: O(1) амортизированно.  Cut — O(1); каскад из c разрезов стоит O(c),
но каждый разрез «оплачен» ранее поставленной меткой (см. лемму 5).
Корректность: вырезание узла в корень не может нарушить свойство кучи;
правило меток гарантирует, что узлы не теряют слишком много детей.

Разбор на примере. Узел [math]\displaystyle{ x }[/math] с ключом 7 уменьшают до 0; ключ родителя 4 больше нового ключа 0, поэтому свойство кучи нарушено — Cut переносит узел с ключом 0 в корни (рис. 3). Если родитель 4 уже был помечен, его тоже вырезают, а пометка «поднимается» к деду (рис. 4).

Крайний случай. Если узел уже корень, Cut не нужен. Если после уменьшения ключ не меньше ключа родителя, свойство кучи не нарушено и разрезов нет.

Рис. 3. Cut(x, y): узел с уменьшенным ключом вырезается из списка детей родителя и становится корнем; degree(y) уменьшается, mark(x) снимается.

Рис. 4. Cascading-Cut: если родитель уже помечен, его тоже вырезают и поднимаются выше; первый непомеченный предок получает метку, и каскад останавливается.

Операция: извлечение минимума (Extract-Min)

Идея. Удалить корень min; его детей сделать корнями; затем консолидировать список корней, сливая деревья равной степени через Link, пока степени не станут попарно различны.

Пошаговое описание.

1. Запомнить [math]\displaystyle{ z = \text{min}[H] }[/math].
2. Каждого ребёнка [math]\displaystyle{ z }[/math] добавить в список корней и обнулить у него parent.
3. Удалить [math]\displaystyle{ z }[/math] из списка корней.
4. Если список корней непуст, Consolidate(H) (важно, чтобы каждая пара равных степеней слилась); иначе min = NIL.
5. Уменьшить счётчик, вернуть [math]\displaystyle{ z }[/math].

Инвариант. После Consolidate степени корней попарно различны; min указывает на корень с наименьшим ключом.

Псевдокод.

Алгоритм Fibonacci-Heap-Extract-Min(H)
Вход:  H — непустая куча
Выход: узел-минимум z; куча без него
1  z ← min[H]
2  if z ≠ NIL
3      for each ребёнок x узла z
4          добавить x в список корней H
5          parent[x] ← NIL
6      удалить z из списка корней H
7      if z = right[z]
8          min[H] ← NIL
9      else
10         min[H] ← right[z]
11         Consolidate(H)
12     n[H] ← n[H] − 1
13 return z

Алгоритм Consolidate(H)
Вход:  H — куча с непустым списком корней
Выход: степени корней попарно различны; min[H] обновлён
1  A[0..D(n[H])] ← NIL                    # A[d] — корень степени d
2  for each корень w в списке корней H
3      x ← w
4      d ← degree[x]
5      while A[d] ≠ NIL
6          y ← A[d]
7          if key[x] > key[y]
8              swap(x, y)
9          Fibonacci-Heap-Link(H, y, x)   # y — ребёнок x
10         A[d] ← NIL
11         d ← d + 1
12     A[d] ← x
13 min[H] ← NIL
14 for i ← 0 to D(n[H])
15     if A[i] ≠ NIL
16         добавить A[i] в список корней H
17         if min[H] = NIL or key[A[i]] < key[min[H]]
18             min[H] ← A[i]

Сложность: O(D(n) + t) фактически, амортизированно O(D(n)) = O(log n).
Корректность: каждое дерево в A[d] имеет степень d; перед помещением в A[d]
все деревья степени d уже слиты, поэтому степени попарно различны.

Разбор на примере. Минимум [math]\displaystyle{ z=1 }[/math] — корень степени 2 с детьми 5 и 8 (у 8 есть ребёнок 9); в списке корней есть ещё корень 12 степени 1 с ребёнком 15. После удаления [math]\displaystyle{ z }[/math] корнями становятся 5, 8 и 12. В Consolidate у 8 и 12 одинаковая степень 1, поэтому Link(12, 8) делает 12 ребёнком 8; остаются корни 5 (степень 0) и 8 (степень 2, дети 12 и 9) — см. рис. 5.

Крайние случаи. Единственный элемент — куча пустеет. Если дети отсутствуют, Consolidate всё равно упорядочивает список корней, сливая совпадающие степени.

Рис. 5. Extract-Min: корень-минимум 1 удаляется, его дети 5 и 8 становятся корнями. В списке оказываются три корня — 5, 8 и 12, — и Consolidate связывает 8 и 12 равной степени 1: остаются корни 5 и 8.

Операция: удаление произвольного узла (Delete)

Идея. Узел удаляется в два шага: его ключ делают бесконечно малым, чтобы он стал минимумом, а затем извлекают минимум обычным способом.

Пошаговое описание.

1. Decrease-Key(H, x, −∞): ключ узла становится меньше ключа родителя, поэтому Cut переносит [math]\displaystyle{ x }[/math] в корни (при необходимости с каскадом); свойство кучи восстанавливается.
2. Extract-Min(H): [math]\displaystyle{ x }[/math] — строгий минимум, поэтому извлекается именно он, а не другой узел.
3. Дети [math]\displaystyle{ x }[/math] при этом становятся корнями, а лес консолидируется.

Инвариант. После шага 1 узел [math]\displaystyle{ x }[/math] — корень с ключом [math]\displaystyle{ -\infty }[/math], то есть единственный минимум кучи; значит, Extract-Min удаляет ровно [math]\displaystyle{ x }[/math] и не может удалить чужой узел.

Псевдокод.

Алгоритм Fibonacci-Heap-Delete(H, x)
Вход:  H — фибоначчиева куча; x — удаляемый узел
Выход: H без узла x; дети x перенесены в список корней
Инвариант: после шага 1 x — корень с ключом −∞, то есть min[H] = x

1  Fibonacci-Heap-Decrease-Key(H, x, −∞)
2  Fibonacci-Heap-Extract-Min(H)

Сложность: амортизированно O(log n) — Decrease-Key даёт O(1), Extract-Min O(log n);
память O(1) сверх уже занятой узлами.
Корректность: шаг 1 сохраняет инвариант кучи и делает x минимумом, шаг 2 удаляет
именно минимум, поэтому удалён ровно x.

Разбор на примере. Возьмём состояние после Consolidate (рис. 5): корни 5 (степень 0) и 8 (степень 2, дети 12 и 9); у узла 12 есть ребёнок 15. Удаляем узел 12: Decrease-Key(12, −∞) уменьшает ключ ниже ключа родителя 8, Cut(12, 8) вырезает 12 в корни (степень 8 падает с 2 до 1), а Cascading-Cut(8) ничего не делает — 8 корень, родителя у него нет. Затем Extract-Min удаляет узел с ключом [math]\displaystyle{ -\infty }[/math] и переносит его ребёнка 15 в корни: в списке оказываются 5 (степень 0), 15 (степень 0) и 8 (степень 1). Consolidate сливает равные степени: Link(15, 5), затем Link(8, 5) — остаётся одно дерево с корнем 5, его дети 15 и 8 (у 8 свой ребёнок 9). Свойство кучи выполнено: 5 ≤ 8, 5 ≤ 15, 8 ≤ 9. Именно перенос детей делает здесь Extract-Min дороже простого удаления: корень 15 добавляется в список и вызывает две операции Link.

Крайние случаи. Если удаляется корень, Cut не нужен: Decrease-Key только меняет ключ, и работа целиком ложится на Extract-Min. Удаление единственного элемента оставляет min[H] = NIL. В реализации вместо литерала [math]\displaystyle{ -\infty }[/math] берут ключ, меньший всех допустимых (например, std::numeric_limits<T>::lowest()), либо отдельный флаг «удалён».

Реализация структуры на C++

Класс min-кучи с циклическими двусвязными списками корней и детей, метками и консолидацией. Отдельно хранятся root_ (голова списка корней) и min_ (минимум). validate() проверяет свойство кучи, циклическую связность, согласованность степеней и родительских ссылок, непомеченность корней и совпадение числа узлов со счётчиком.

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <stdexcept>

template <typename T>
class FibonacciHeap {
public:
    struct Node {
        T key;
        int degree = 0;
        bool mark = false;
        Node *parent = nullptr, *child = nullptr, *left = nullptr, *right = nullptr;
        explicit Node(const T& k) : key(k), left(this), right(this) {}
    };

private:
    Node* root_ = nullptr;   // голова циклического списка корней
    Node* min_ = nullptr;    // корень с минимальным ключом
    std::size_t n_ = 0;

    static void addToList(Node*& head, Node* x) {
        if (!head) { head = x; x->left = x->right = x; return; }
        x->right = head;
        x->left = head->left;
        head->left->right = x;
        head->left = x;
    }

    static void removeFromList(Node*& head, Node* x) {
        if (x->right == x) { head = nullptr; }
        else {
            x->left->right = x->right;
            x->right->left = x->left;
            if (head == x) head = x->right;
        }
        x->left = x->right = x;
    }

    static void link(Node* y, Node* x) {          // y — ребёнок x; key[x] <= key[y]
        y->parent = x;
        y->mark = false;
        y->left = y->right = y;
        if (!x->child) x->child = y;
        else addToList(x->child, y);
        x->degree += 1;
    }

    void cut(Node* x, Node* y) {                  // вырезать x из детей y в корни
        if (x->right == x) y->child = nullptr;
        else removeFromList(y->child, x);
        y->degree -= 1;
        x->parent = nullptr;
        x->mark = false;
        x->left = x->right = x;
        addToList(root_, x);
    }

    void cascadingCut(Node* y) {
        Node* z = y->parent;
        if (!z) return;
        if (!y->mark) y->mark = true;
        else { cut(y, z); cascadingCut(z); }
    }

    void consolidate() {
        std::vector<Node*> A;
        std::vector<Node*> roots;
        if (root_) {
            Node* x = root_;
            do { roots.push_back(x); x = x->right; } while (x != root_);
        }
        for (Node* w : roots) {
            Node* x = w;
            int d = x->degree;
            while (d < static_cast<int>(A.size()) && A[d]) {
                Node* y = A[d];
                if (x->key > y->key) std::swap(x, y);
                link(y, x);
                A[d] = nullptr;
                ++d;
            }
            if (d >= static_cast<int>(A.size())) A.resize(d + 1, nullptr);
            A[d] = x;
        }
        root_ = nullptr;
        min_ = nullptr;
        for (Node* x : A) {
            if (!x) continue;
            x->parent = nullptr;
            x->left = x->right = x;
            addToList(root_, x);
            if (!min_ || x->key < min_->key) min_ = x;
        }
    }

    static void destroyNodes(Node* start) {
        if (!start) return;
        Node* x = start;
        do {
            Node* next = x->right;
            destroyNodes(x->child);
            delete x;
            x = next;
        } while (x != start);
    }

    bool checkNode(Node* x) const {
        int children = 0;
        if (x->child) {
            Node* c = x->child;
            do {
                if (c->parent != x) return false;
                if (x->key > c->key) return false;      // min-куча
                if (!checkNode(c)) return false;
                ++children;
                c = c->right;
                if (children > 1000000000) return false;
            } while (c != x->child);
        }
        return children == x->degree;
    }

    static Node* findNode(Node* start, const T& k) {
        if (!start) return nullptr;
        Node* x = start;
        do {
            if (x->key == k) return x;
            if (Node* r = findNode(x->child, k)) return r;
            x = x->right;
        } while (x != start);
        return nullptr;
    }

public:
    FibonacciHeap() = default;
    ~FibonacciHeap() { destroyNodes(root_); }
    FibonacciHeap(const FibonacciHeap&) = delete;
    FibonacciHeap& operator=(const FibonacciHeap&) = delete;

    bool empty() const { return min_ == nullptr; }
    std::size_t size() const { return n_; }
    const T& minimum() const {                 // предусловие: куча непуста
        if (!min_) throw std::out_of_range("пустая куча");
        return min_->key;
    }

    Node* insert(const T& k) {                    // O(1)
        Node* x = new Node(k);
        addToList(root_, x);
        if (!min_ || x->key < min_->key) min_ = x;
        ++n_;
        return x;
    }

    bool pop(T& out) {                            // Extract-Min
        if (!min_) return false;
        Node* z = min_;
        out = z->key;
        if (z->child) {                           // детей — в список корней
            Node* start = z->child;
            Node* c = start;
            do {
                Node* next = c->right;
                c->parent = nullptr;
                c->mark = false;
                c->left = c->right = c;
                addToList(root_, c);
                c = next;
            } while (c != start);
            z->child = nullptr;
        }
        removeFromList(root_, z);
        if (root_) { min_ = root_; consolidate(); }
        else min_ = nullptr;
        delete z;
        --n_;
        return true;
    }

    void decreaseKey(Node* x, const T& k) {       // амортизированно O(1)
        if (k > x->key) throw std::invalid_argument("новый ключ больше текущего");
        x->key = k;
        Node* y = x->parent;
        if (y && x->key < y->key) {
            cut(x, y);
            cascadingCut(y);
        }
        if (min_ && x->key < min_->key) min_ = x;
    }

    void merge(FibonacciHeap& other) {            // O(1)
        if (!other.root_) { return; }
        if (!root_) {
            root_ = other.root_;
            min_ = other.min_;
        } else {
            Node* a = root_;
            Node* b = other.root_;
            a->right->left = b->left;             // сцепка двух циклических списков
            b->left->right = a->right;
            a->right = b;
            b->left = a;
            if (other.min_->key < min_->key) min_ = other.min_;
        }
        n_ += other.n_;
        other.root_ = nullptr;
        other.min_ = nullptr;
        other.n_ = 0;
    }

    bool contains(const T& k) const { return findNode(root_, k) != nullptr; }

    bool validate() const {
        if (!root_) return min_ == nullptr && n_ == 0;
        std::size_t count = 0;
        Node* x = root_;
        do {
            if (x->parent) return false;
            if (x->mark) return false;                 // корни не помечены
            if (!checkNode(x)) return false;
            count += subtreeSize(x);
            x = x->right;
            if (count > n_) return false;
        } while (x != root_);
        if (count != n_) return false;
        if (!min_ || min_->parent) return false;
        Node* it = root_;
        do { if (it->key < min_->key) return false; it = it->right; } while (it != root_);
        return true;
    }

    std::size_t subtreeSize(Node* x) const {
        std::size_t s = 1;
        if (x->child) {
            Node* c = x->child;
            do { s += subtreeSize(c); c = c->right; } while (c != x->child);
        }
        return s;
    }
};

int main() {
    // 1) decrease-key от 9 до -5
    FibonacciHeap<int> h;
    auto n9 = h.insert(9);
    h.insert(4); h.insert(6); h.insert(2); h.insert(8);
    assert(h.validate());
    assert(h.minimum() == 2);
    h.decreaseKey(n9, -5);
    assert(h.validate());
    assert(h.minimum() == -5);
    int m; assert(h.pop(m) && m == -5);
    assert(h.validate());

    // 2) слияние за O(1) и извлечение по возрастанию
    FibonacciHeap<int> a, b;
    for (int v : {1, 3, 5, 7, 9}) a.insert(v);
    for (int v : {2, 4, 6, 8, 10}) b.insert(v);
    a.merge(b);
    assert(a.validate());
    std::vector<int> out; int x;
    while (a.pop(x)) out.push_back(x);
    assert(std::is_sorted(out.begin(), out.end()));
    assert(out.size() == 10);

    // 3) стресс: каскадные отсечения
    FibonacciHeap<int> s;
    std::vector<FibonacciHeap<int>::Node*> ns;
    const int N = 1000;
    for (int i = 0; i < N; ++i) ns.push_back(s.insert(N - i));
    assert(s.validate());
    for (int i = 0; i < N; i += 2) s.decreaseKey(ns[i], -i - 1);
    assert(s.validate());
    std::vector<int> all;
    while (s.pop(x)) all.push_back(x);
    assert(std::is_sorted(all.begin(), all.end()));
    assert(all.size() == static_cast<std::size_t>(N));

    // 4) minimum() на пустой куче
    FibonacciHeap<int> e;
    bool threw = false;
    try { e.minimum(); } catch (const std::out_of_range&) { threw = true; }
    assert(threw);

    std::cout << "ok\n";
    return 0;
}

Замечания по реализации.

• roots собирается в вектор перед консолидацией: исходный список корней меняется в ходе слияний, обходить его «на живую» нельзя.
• link увеличивает degree родителя, cut — уменьшает: эти счётчики поддерживают согласованность структуры; граница [math]\displaystyle{ D(n) = O(\log n) }[/math] следует из правила меток (лемма 2).
• Дети при Extract-Min переносятся как отдельные корни; их метки снимаются.
• merge не сливает деревья — только сцепляет списки, поэтому [math]\displaystyle{ O(1) }[/math].
• Копирование отключено: корректная копия должна клонировать весь лес.

Сводная таблица сложности

Операция	Фактическая (худшая)	Амортизированная	Память
Make-Heap	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Insert	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Find-Min	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Union / Merge	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Extract-Min	[math]\displaystyle{ O(D(n) + t) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Decrease-Key	[math]\displaystyle{ O(c) }[/math] ([math]\displaystyle{ c }[/math] разрезов)	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Delete	[math]\displaystyle{ O(D(n) + t) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]

Примечание. Границы Decrease-Key и Extract-Min — амортизированные, а не худшие: отдельная Decrease-Key может вызвать длинный каскад из [math]\displaystyle{ O(\log n) }[/math] разрезов, а отдельный Extract-Min может стоить [math]\displaystyle{ O(n) }[/math] при большом списке корней. Именно накопление и «разбор» беспорядка дают амортизированные оценки. [math]\displaystyle{ D(n) = O(\log n) }[/math] — граница максимальной степени (см. раздел «Корректность и оценка сложности»).

Трассировка примера

Проследим каскадное отсечение на цепочке [math]\displaystyle{ p(1) \to r(2) \to y(4) \to x(7) }[/math], где [math]\displaystyle{ y }[/math] уже помечен. Уменьшаем ключ [math]\displaystyle{ x }[/math] с 7 до 0. Узел [math]\displaystyle{ r }[/math] — внутренний: каскад остановится именно на нём, потому что он ещё не помечен.

Шаг	Действие	Состояние	Пометки
0	исходно	p(1) → r(2) → y(4) → x(7)	mark(y) = true
1	key[x] ← 0	0 < 4 — нарушение свойства кучи	mark(y) = true
2	Cut(x, y)	x(0) — корень; p → r → y(4)	mark(x) = false
3	Cascading-Cut(y): mark(y) = true →	Cut(y, r); y(4) — корень	mark(y) = false
4	Cascading-Cut(r): mark(r) = false →	пометить r, стоп; r остаётся ребёнком p	mark(r) = true
5	обновить min	min = x(0), если он наименьший	—

Итог: [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] стали корнями (два дерева добавились — растёт [math]\displaystyle{ t }[/math]); при этом снята одна метка (y) и поставлена одна новая (r), поэтому [math]\displaystyle{ \Delta\Phi = 2 + 2(1-1) = 2 }[/math], что согласуется с оценкой [math]\displaystyle{ \Delta\Phi \le 4 - c }[/math] при [math]\displaystyle{ c = 2 }[/math]. Выше стоит [math]\displaystyle{ p }[/math] — корень; Cascading-Cut для корня ничего не делает, потому что у него нет родителя.

Корректность и оценка сложности

Лемма 1 (свойство кучи сохраняется). Link, Cut, Insert, Union, Consolidate не нарушают свойство min-кучи.

Доказательство. Link делает родителем узел с меньшим ключом, поэтому для новой пары свойство выполнено; внутри поддеревьев ничего не менялось. Cut переносит узел в корни — у корня нет родителя, ограничение снимается, но узел мог стать меньше своего бывшего родителя, что допустимо. Consolidate применяет только Link. Остальные операции лишь меняют списки. [math]\displaystyle{ \blacksquare }[/math]

Лемма 2 (граница степени). Узел степени [math]\displaystyle{ k }[/math] в фибоначчиевой куче имеет поддерево размером не менее [math]\displaystyle{ F_{k+2} \ge \varphi^{\,k} }[/math], где [math]\displaystyle{ F_1 = F_2 = 1 }[/math]. Следовательно, максимальная степень [math]\displaystyle{ D(n) = O(\log n) }[/math].

Доказательство. Пусть [math]\displaystyle{ x }[/math] имеет степень [math]\displaystyle{ k }[/math], а его дети — [math]\displaystyle{ c_1, \dots, c_k }[/math] в порядке присоединения. Когда [math]\displaystyle{ c_i }[/math] стал ребёнком [math]\displaystyle{ x }[/math], у [math]\displaystyle{ x }[/math] было уже [math]\displaystyle{ i-1 }[/math] детей; Link соединяет только корни равной степени, поэтому в момент присоединения [math]\displaystyle{ \text{degree}(c_i) = \text{degree}(x) = i-1 }[/math]. С тех пор [math]\displaystyle{ c_i }[/math] потерял не более одного ребёнка (иначе был бы вырезан меткой), поэтому теперь [math]\displaystyle{ \text{degree}(c_i) \ge i-2 }[/math]. По индукции размер поддерева [math]\displaystyle{ \ge F_{k+2} }[/math]; так как [math]\displaystyle{ F_{k+2} \ge \varphi^k }[/math], из [math]\displaystyle{ n \ge F_{k+2} }[/math] получаем [math]\displaystyle{ k \le \log_\varphi n }[/math]. [math]\displaystyle{ \blacksquare }[/math]

Лемма 3 (Union и Find-Min). Insert, Find-Min, Union выполняются за [math]\displaystyle{ O(1) }[/math] амортизированно.

Доказательство. Каждая из операций делает [math]\displaystyle{ O(1) }[/math] работы со списками. Insert увеличивает потенциал на 1 (одно новое дерево), так что амортизированная стоимость [math]\displaystyle{ \hat c = O(1) + 1 = O(1) }[/math]. Union не меняет число деревьев и меток, [math]\displaystyle{ \Delta\Phi = 0 }[/math]. [math]\displaystyle{ \blacksquare }[/math]

Лемма 4 (стоимость Extract-Min). Extract-Min — амортизированно [math]\displaystyle{ O(\log n) }[/math].

Доказательство. Пусть до операции было [math]\displaystyle{ t }[/math] деревьев. Фактическая стоимость [math]\displaystyle{ O(D(n) + t) }[/math]: перенос детей и проход консолидации. После консолидации остаётся не более [math]\displaystyle{ D(n) + 1 }[/math] деревьев, поэтому [math]\displaystyle{ \Delta\Phi \le (D(n)+1) - t }[/math] (плюс возможное изменение меток, но перенос детей метки снимает, так что [math]\displaystyle{ 2m(H) }[/math] не растёт). Амортизированная стоимость:

[math]\displaystyle{ O(D(n) + t) + \bigl(D(n) + 1 - t\bigr) = O(D(n)) = O(\log n). \quad \blacksquare }[/math]

Лемма 5 (стоимость Decrease-Key). Decrease-Key с [math]\displaystyle{ c }[/math] разрезами — амортизированно [math]\displaystyle{ O(1) }[/math].

Доказательство. Фактическая стоимость [math]\displaystyle{ O(c) }[/math]. Каждый Cut добавляет одно дерево ([math]\displaystyle{ +1 }[/math] к [math]\displaystyle{ t }[/math]) и снимает метку вырезанного узла. Из [math]\displaystyle{ c }[/math] разрезов не более одного узла не был помечен (первый — [math]\displaystyle{ x }[/math]), следовательно снято не менее [math]\displaystyle{ c-1 }[/math] меток; кроме того, один предок может получить новую метку ([math]\displaystyle{ +2 }[/math] к [math]\displaystyle{ 2m(H) }[/math]). Итого

[math]\displaystyle{ \Delta\Phi \le c + 2 - 2(c-1) = 4 - c, }[/math]

и амортизированная стоимость [math]\displaystyle{ O(c) + (4 - c) = O(1) }[/math]. [math]\displaystyle{ \blacksquare }[/math]

Схема этого учёта — фактическая стоимость плюс изменение потенциала — показана на рис. 6.

Следствие. Дейкстра на фибоначчиевой куче: [math]\displaystyle{ n }[/math] Extract-Min ([math]\displaystyle{ O(n\log n) }[/math]) и [math]\displaystyle{ m }[/math] Decrease-Key ([math]\displaystyle{ O(m) }[/math] амортизированно) дают [math]\displaystyle{ O(m + n\log n) }[/math].

Рис. 6. Потенциал [math]\displaystyle{ \Phi(H) = t(H) + 2m(H) }[/math]: амортизированная стоимость = фактическая [math]\displaystyle{ +\ \Delta\Phi }[/math]. Для Insert и Decrease-Key она [math]\displaystyle{ O(1) }[/math], для Extract-Min — [math]\displaystyle{ O(\log n) }[/math].

Сравнение с альтернативами

Структура	Insert	Extract-Min	Decrease-Key	Merge	Find-Min
Двоичная куча	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Биномиальная куча	аморт. [math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]
Фибоначчиева куча	[math]\displaystyle{ O(1) }[/math]	аморт. [math]\displaystyle{ O(\log n) }[/math]	аморт. [math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Pairing-куча	[math]\displaystyle{ O(1) }[/math]	аморт. [math]\displaystyle{ O(\log n) }[/math]	аморт. [math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]
Rank-pairing куча	[math]\displaystyle{ O(1) }[/math]	аморт. [math]\displaystyle{ O(\log n) }[/math]	аморт. [math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(1) }[/math]

Вердикт. Фибоначчиева куча — теоретически лучший компромисс для алгоритмов с частым decrease-key и слияниями. На практике её обгоняют двоичная и pairing-кучи из-за больших констант, четырёх указателей и меток на узел, а также плохой локальности кэша. Rank-pairing куча (2009) даёт те же границы при меньшей константе. Сравнение пяти структур по всем операциям — в таблице выше; четыре из них показаны на рис. 7.

Рис. 7. Фибоначчиева куча — единственная из перечисленных на рисунке с амортизированным [math]\displaystyle{ O(1) }[/math] на уменьшение ключа; остальные проигрывают ей по Decrease-Key и/или слиянию.

Где применяется

1. Алгоритм Дейкстры. С [math]\displaystyle{ n }[/math] извлечениями и до [math]\displaystyle{ m }[/math] уменьшениями ключа фибоначчиева куча даёт [math]\displaystyle{ O(m + n\log n) }[/math] против [math]\displaystyle{ O(m\log n) }[/math] у двоичной; выигрыш заметен на разреженных графах [2][3].
2. Алгоритм Прима для минимального остовного дерева — та же схема с decrease-key.
3. Сетевая оптимизация и потоки. Теоретические улучшения для задач о потоках и паросочетаниях опираются на фибоначчиевы (и родственные) кучи [2][3].
4. Boost.Heap (C++). boost::heap::fibonacci_heap — готовая реализация с increase, decrease, update и слиянием; выбирается в задачах, где важны эти операции [5].
5. Учебная и исследовательская база. Фибоначчиева куча — образец амортизационного анализа методом потенциала; из неё выросли pairing-, rank-pairing- и strict-фибоначчиевы кучи.

Историческая справка

• 1978. Ж. Вюйемен предложил биномиальные кучи — предшественника с логарифмическим decrease-key [4].
• 1984. М. Фредман и Р. Тарджан представили фибоначчиевы кучи на конференции FOCS, продемонстрировав амортизированное [math]\displaystyle{ O(1) }[/math] на decrease-key [3].
• 1987. Полная журнальная версия с приложениями к сетевым алгоритмам — Dijkstra и Prim за [math]\displaystyle{ O(m + n\log n) }[/math], улучшения для паросочетаний [2].
• 1986–2009. Появились pairing-кучи (Фредман, Седжвик, Слейтор, Тарджан) [7], затем rank-pairing кучи (Хойплер, Сен, Тарджан) [8] — попытки получить те же границы проще и с меньшими константами.
• Название связано с тем, что минимальный размер поддерева узла степени [math]\displaystyle{ k }[/math] оценивается числом Фибоначчи [math]\displaystyle{ F_{k+2} }[/math] (лемма 2).

Типичные ошибки и подводные камни

• Забыть снять mark у вырезанного узла. После Cut узел — корень, а корни не помечаются.
• Неверное условие каскада. Помечаем родителя только если он ещё не помечен; иначе вырезаем его и продолжаем вверх. Перепутанный порядок ломает амортизацию.
• Обход списка корней «на живую» в Consolidate. Список меняется при Link; нужно сначала собрать корни в отдельную коллекцию.
• Слишком маленький массив A. Его размер должен покрывать [math]\displaystyle{ D(n) = O(\log n) }[/math]; берётся с запасом или расширяется динамически.
• Не обнулить parent у детей при Extract-Min. Иначе validate и логика отсечений увидят некорректные ссылки.
• Считать Decrease-Key константным в худшем случае. [math]\displaystyle{ O(1) }[/math] — только амортизированно; отдельная операция может дать каскад из [math]\displaystyle{ O(\log n) }[/math] разрезов.
• Ошибки в циклических списках. Неверная перепривязка left/right рвёт кольцо — самое коварное место реализации.
• Путать root_ и min_. min_ — указатель на минимум, а не голова списка; обе ссылки надо поддерживать согласованно.
• Ожидать выигрыша на практике автоматически. Из-за констант и памяти фибоначчиева куча часто проигрывает двоичной; выбирайте её, только если decrease-key/слияния действительно доминируют.
• Отсутствие decrease-key в стандартных контейнерах. У std::priority_queue его нет; фибоначчиева куча — одна из структур, где он есть, но требует указателя на узел.

Задачи для практики

1. Свойства и метки. Докажите, что узел теряет не более одного ребёнка, пока не станет корнем. Подсказка: индукция по правилу Cascading-Cut.
2. Граница степени. Докажите [math]\displaystyle{ D(n) = O(\log n) }[/math] через размер поддерева [math]\displaystyle{ F_{k+2} \ge \varphi^k }[/math]. Подсказка: оцените степени детей в порядке присоединения.
3. Потенциальный анализ. Выведите амортизированную стоимость Extract-Min и Decrease-Key с [math]\displaystyle{ \Phi(H) = t(H) + 2m(H) }[/math]. Подсказка: аккуратно посчитайте изменение числа деревьев и меток.
4. Удаление узла. Реализуйте Delete(H, x) через Decrease-Key(x, −∞) и Extract-Min; докажите амортизированное [math]\displaystyle{ O(\log n) }[/math].
5. Слияние за [math]\displaystyle{ O(1) }[/math]. Реализуйте merge (сцепку двух циклических списков) и проверьте его стоимость на длинных списках.
6. Дейкстра на двух кучах. Сравните на разреженном графе ([math]\displaystyle{ n=10^5 }[/math], [math]\displaystyle{ m=5\cdot10^5 }[/math]) двоичную и фибоначчиеву кучи. Подсказка: считайте число вызовов decrease-key.
7. Извлечение по возрастанию. Реализуйте Extract-Min и убедитесь, что повторные извлечения выдают ключи по неубыванию; проверьте все инварианты после каждого шага.
8. Устойчивость к каскадам. Сгенерируйте данные, провоцирующие длинные каскадные отсечения, и измерьте суммарную (а не отдельную) стоимость — она должна быть линейной.

Связанные темы

• Биномиальная куча — идейный предшественник с [math]\displaystyle{ O(\log n) }[/math] на decrease-key.
• Двоичная куча — простая и быстрая на практике, но без быстрого decrease-key и слияния.
• Очередь с приоритетом — абстрактный тип данных.
• Алгоритм Дейкстры — главный потребитель decrease-key.
• Алгоритм Прима — минимальное остовное дерево.
• Амортизационный анализ — метод потенциала.
• Асимптотическая сложность — нотация [math]\displaystyle{ O }[/math], [math]\displaystyle{ \Omega }[/math], [math]\displaystyle{ \Theta }[/math].

Источники

1. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 19 «Fibonacci Heaps» (в 2-м изд. — гл. 20).
2. Fredman M. L., Tarjan R. E. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms // Journal of the ACM. — 1987. — Vol. 34, No. 3. — P. 596–615.
3. Fredman M. L., Tarjan R. E. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms // Proceedings of the 25th Annual Symposium on Foundations of Computer Science (FOCS). — 1984. — P. 338–346.
4. Vuillemin J. A Data Structure for Manipulating Priority Queues // Communications of the ACM. — 1978. — Vol. 21, No. 4. — P. 309–315.
5. Boost.Heap: fibonacci_heap. URL: https://www.boost.org/doc/libs/release/doc/html/heap.html.
6. Wikipedia: Fibonacci heap. URL: https://en.wikipedia.org/wiki/Fibonacci_heap.
7. Fredman M. L., Sedgewick R., Sleator D. D., Tarjan R. E. The Pairing Heap: A New Form of Self-Adjusting Heap // Algorithmica. — 1986. — Vol. 1, No. 1. — P. 111–129.
8. Haeupler B., Sen S., Tarjan R. E. Rank-Pairing Heaps // Algorithms — ESA 2009. — Springer, 2009.