Куча Фибоначчи: уменьшение ключа за O(1) и чем за это платят

Если ты знаешь про ленивое слияние, разрез с пометкой, каскадный разрез и уплотнение при извлечении - и понимаешь, откуда в оценке берутся числа Фибоначчи, листай до «Теперь сам».

Как думаешь, можно ли не просеивать при уменьшении ключа

В биномиальной куче уменьшение ключа просеивает узел вверх по дереву - O(log n). Прежде чем читать дальше, подумай: а обязательно ли вообще оставлять узел в этом дереве? Что мешает выдернуть его вместе с поддеревом и объявить отдельным деревом леса? Свойство кучи внутри вырезанного поддерева не пострадает - все его узлы больше своего корня, а корень стал только меньше. Значит мешать может лишь одно: форма. Вот о ней весь урок.

На что это похоже

Уборка в мастерской двумя способами. Первый: класть каждый инструмент на место сразу - порядок идеальный, но каждое действие чуть дороже. Второй: бросать всё на верстак и разбирать завал только тогда, когда понадобилось найти нужный ключ, - зато разбирать сразу и целиком, раскладывая по ящикам похожее к похожему. Второй способ выгоднее, если ищут редко, а кладут часто. Но у него есть условие: нельзя разрешать растаскивать уже разложенное без ограничений, иначе ящики опустеют и раскладка перестанет помогать.

Механизм: ленивость плюс правило одной потери

структура    : кольцевой двусвязный список КОРНЕЙ (лес) + указатель на минимальный
               корень. Кольцо потому, что два кольца сцепляются в одно перестановкой
               четырёх ссылок - за O(1) и не зная их длин; у обычного списка пришлось
               бы дойти до хвоста
               у каждого узла: степень (число детей) и ПОМЕТКА «терял ли ребёнка»

insert(x)    : добавить дерево из одного узла в список корней,
               поправить указатель минимума                       O(1)
merge(A, B)  : сцепить два списка корней                          O(1)
min()        : взять указатель                                    O(1)

decrease_key(v, new):
               уменьшить ключ; если стало меньше родителя:
                 ОТРЕЗАТЬ v с поддеревом в список корней, снять с него пометку
                 подняться к родителю: не помечен - пометить и остановиться;
                 уже помечен - отрезать и его тоже (КАСКАДНЫЙ РАЗРЕЗ), и так вверх
               если новый ключ меньше минимального - переставить указатель минимума
                                                                  O(1) амортизированно
extract_min():
               убрать минимальный корень, его детей - в список корней (пометки с них снять),
               УПЛОТНИТЬ: завести массив «степень → корень» длиной 1.44·log₂ n и пройти
               по всем корням: если ячейка занята - соединить два корня (ребёнком
               становится тот, чей ключ хуже) и повторить со степенью на единицу больше;
               новый минимум ищут тем же проходом по корням  O(log n) амортизированно

Уплотнение - это та же операция, что в биномиальной куче, но отложенная: после неё степени всех корней снова различны, и деревьев снова O(log n).

Правило

Куча Фибоначчи держит лес и откладывает всю уборку: insert, merge, min - O(1); decrease_key отрезает узел в список корней и стоит O(1) амортизированно; extract_min уплотняет лес (соединяет корни равной степени) за O(log n) амортизированно. Узел, потерявший ПЕРВОГО ребёнка, помечается; потеря второго отрезает его самого - каскадный разрез. Из правила следует, что поддерево узла степени k содержит не меньше F_{k+2} ≥ φ^k узлов, значит степень не больше 1.44·log₂ n. Дейкстра и Прим на такой куче - O(E + V·log V).

Разбор: каскадный разрез по шагам

Пусть в дереве есть цепочка: узел A (корень дерева), у него ребёнок B, у B - ребёнок C, у C - ребёнок D. Пусть B и C УЖЕ помечены (каждый однажды терял ребёнка), а A не помечен. Уменьшаем ключ узла D так, что он становится меньше ключа C.

1. Свойство кучи нарушено (D < C). Отрезаем D вместе с его поддеревом и кладём в список корней; пометку с D снимаем - корни не помечаются никогда.
2. Поднимаемся к родителю C: он потерял ребёнка. C уже помечен - значит это его ВТОРАЯ потеря. Отрезаем C (с оставшимся поддеревом) в список корней, снимаем с него пометку.
3. Поднимаемся к B: он тоже потерял ребёнка (C ушёл) и тоже уже помечен - вторая потеря. Отрезаем B в список корней, пометку снимаем.
4. Поднимаемся к A: он потерял ребёнка B, но НЕ помечен. Помечаем его и останавливаемся.

Итог: три разреза, список корней вырос на три дерева. Почему это всё равно O(1) в среднем: каждый каскадный разрез СНИМАЕТ пометку, а пометка появляется только при обычной потере ребёнка, которая уже оплачена своей операцией. В терминах потенциала (это метод из раздела про амортизацию) берут Φ = t + 2m, где t - число деревьев, m - число помеченных узлов: каждый каскадный разрез добавляет дерево (+1) и снимает пометку (−2), то есть уменьшает потенциал, оплачивая свою работу. Длинная цепочка разрезов возможна, но она означает, что до неё было много дешёвых операций, накопивших пометки.

Считаем вместе: откуда числа Фибоначчи и граница 1.44·log₂ n

Правило «не больше одной потери» и даёт название структуры. Рассуждение такое. Пусть у узла v степень k, а его дети перечислены в порядке, в котором их подвешивали: y₁, y₂, ..., y_k. В момент, когда подвешивали y_i, у v уже было не меньше i−1 детей, а соединяют только корни РАВНОЙ степени - значит степень y_i тогда была не меньше i−1. После этого y_i мог потерять не больше одного ребёнка (второй запустил бы каскадный разрез и отрезал самого y_i), значит сейчас его степень не меньше i−2.

Обозначим S_k наименьшее возможное число узлов в поддереве узла степени k:

S₀ = 1,  S₁ = 2,  S_k = 2 + S₀ + S₁ + ... + S_(k−2)

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

S_k     = 2 + S₀ + S₁ + ... + S_(k−3) + S_(k−2)
S_(k−1) = 2 + S₀ + S₁ + ... + S_(k−3)
S_k − S_(k−1) = S_(k−2)   →   S_k = S_(k−1) + S_(k−2)

Это в точности закон Фибоначчи. С начальными S₀ = 1, S₁ = 2 получаем S_k = F_(k+2) при ИНДЕКСАЦИИ F₀ = 0, F₁ = F₂ = 1, F₃ = 2, F₄ = 3, F₅ = 5, F₆ = 8 (индексация здесь важна: со сдвигом формула перестанет сходиться). Проверим: S₀ = 1 = F₂, S₁ = 2 = F₃, S₂ = 3 = F₄, S₃ = 5 = F₅.

Отдельная лемма: F_(k+2) ≥ φ^k, где φ = (1+√5)/2 ≈ 1.618 - корень уравнения φ² = φ + 1. Доказывается индукцией: для k = 0 и k = 1 проверяется напрямую (1 ≥ 1, 2 ≥ 1.618), а шаг - F_(k+2) = F_(k+1) + F_k ≥ φ^(k−1) + φ^(k−2) = φ^(k−2)·(φ + 1) = φ^(k−2)·φ² = φ^k. Значит n ≥ φ^k, откуда

k <= log_φ n = log₂ n / log₂ φ ≈ log₂ n / 0.694 ≈ 1.44 · log₂ n

Вот и ответ: степень любого узла - O(log n), поэтому массив «степень → корень» при уплотнении имеет длину O(log n), и после уплотнения корней остаётся не больше O(log n).

Но отсюда НЕ следует, что один extract_min дёшев, и это место стоит проговорить. Перед уплотнением корней может быть сколько угодно - ленивые вставки и разрезы кладут их в список пачками, до Θ(n); значит отдельное извлечение может честно пройти по всем корням и стоить линейно. Логарифм получается только АМОРТИЗИРОВАННО: проход по t корням уменьшает число деревьев до O(log n), то есть роняет потенциал Φ = t + 2m примерно на t, и эта работа уже оплачена теми дешёвыми операциями, которые корни создали. Ровно за этим сюда и позван метод потенциалов из раздела про амортизацию.

Убери правило одной потери - и деревья выродятся: узел большой степени сможет остаться почти пустым, граница исчезнет, а вместе с ней и все оценки.

Разбор: почему это важно для Дейкстры

Алгоритм Дейкстры ищет кратчайшие пути от одной вершины ко всем остальным; подробно он разобран в разделе про кратчайшие пути, а здесь достаточно его скелета в терминах нашего контракта. Есть сеть из V точек и E связей между ними с длинами. Все точки лежат в очереди с приоритетами, где приоритет - текущая оценка расстояния. Алгоритм V раз берёт ближайшую точку (pop) и для каждой связи, ведущей из неё, пробует улучшить оценку соседа (decrease_key) - то есть уменьшений ключа не больше, чем связей, E. Вся его цена - это цена V извлечений плюс E уменьшений:

двоичная куча   : V·log V + E·log V = O((V + E)·log V)
куча Фибоначчи  : V·log V + E·1     = O(E + V·log V)

На РАЗРЕЖЕННОМ графе (E ≈ V) обе дают O(V·log V) - разницы нет. На ПЛОТНОМ (E ≈ V²) двоичная даёт V²·log V, а Фибоначчи - V²: выигрыш в логарифм. Именно этот случай и был целью, когда кучу придумывали: она убирает логарифм из самого частого слагаемого. Та же математика работает для алгоритма Прима (он строит минимальное остовное дерево и точно так же на каждом шаге берёт ближайшую точку и улучшает оценки соседей - раздел про остовные деревья) и для некоторых алгоритмов потока.

Дальше начинается честная часть. Константы у кучи Фибоначчи большие: на узел нужно четыре указателя (родитель, ребёнок, два соседа по кольцу), степень и пометка; память разбросана, кеш промахивается, код сложный и легко ломается на каскадных разрезах. В измерениях на реальных графах двоичная куча с ЛЕНИВЫМ удалением (из прошлой главы) обычно обгоняет кучу Фибоначчи, а среди сливаемых структур практический выбор - спаривающаяся (pairing) куча: у неё почти те же амортизированные оценки, а кода в разы меньше. Поэтому вывод такой: куча Фибоначчи - это доказательство, что O(E + V·log V) достижимо, и инструмент для теоретических границ; в прикладном коде её ставят редко и осознанно.

Что ломается без этого

Первое: отрезать узел без пометки родителя - правило «одна потеря» исчезнет, деревья выродятся, степень перестанет быть O(log n), и extract_min станет линейным. Второе: помечать корни - корень никого не теряет в смысле правила, пометку с него снимают при попадании в список корней. Третье: ждать O(1) от КАЖДОГО уменьшения ключа - оценка амортизированная, отдельный вызов может запустить длинный каскад. Четвёртое: забыть обновить указатель минимума после decrease_key (новый ключ мог стать минимальным) - куча начнёт возвращать не минимум. Пятое, самое частое на практике: взять кучу Фибоначчи «потому что она асимптотически лучшая» и получить код, который медленнее двоичной кучи в разы и содержит вдвое больше ошибок.

Зачем это в работе

Прямых применений мало, и это нормально: ценность урока в двух вещах. Первая - приём ЛЕНИВОСТИ как инструмент проектирования. «Не наводить порядок сразу, а сложить работу в кучу и разобрать её один раз, когда всё равно придётся» - это общий шаблон, и он встречается всюду: ленивое удаление в очередях, отложенные обновления в дереве отрезков, сборка мусора, буферизация записи в базах, перестройка индексов пачкой, LSM-деревья в современных хранилищах. Куча Фибоначчи - предельный случай этого шаблона. Вторая - умение читать оценку алгоритма как СУММУ слагаемых по операциям и понимать, какое слагаемое доминирует: O(E + V·log V) против O((V+E)·log V) - это не соревнование структур, а ответ на вопрос «чего в моей задаче больше: извлечений или уменьшений ключа». Именно так и выбирают структуру: считают операции, а не сравнивают названия.

Теперь сам

Граф из 1000 вершин, 500 000 рёбер (плотный). Оцени число элементарных операций для Дейкстры на двоичной куче и на куче Фибоначчи, считая log₂ 1000 ≈ 10. Во сколько раз отличаются оценки и означает ли это такой же выигрыш по времени?