# конспект · шаг 6 из 6
Конспект: сливаемые кучи
Понятия
Почему двоичная куча не сливается - она держит форму полного дерева ради укладки в массив, а
два полных дерева не дают полного без переукладки: слияние Θ(n). Дешёвое слияние требует ЛЕСА
деревьев на указателях.
Биномиальное дерево B_k - два B_{k−1}, сцепленных корнями (ребёнком становится корень с
худшим ключом): 2^k узлов, высота k, k детей у корня, C(k, d) узлов на глубине d.
Биномиальная куча - лес деревьев разных размеров; их набор совпадает с двоичной записью n
(13 = 1101₂ → B₃, B₂, B₀), деревьев не больше ⌊log₂ n⌋ + 1. Слияние - сложение столбиком с
переносом.
Куча Фибоначчи - лес, в котором порядок не наводят до последнего: список корней плюс указатель на минимум, у узла степень и пометка.
Каскадный разрез - узел, потерявший первого ребёнка, помечается; при второй потере отрезается сам, и так вверх. Пометка с корня снимается.
Граница степени - из правила одной потери: узел степени k держит не меньше F_{k+2} ≥ φ^k
узлов в поддереве (считая себя), значит степень ≤ 1.44·log₂ n. Отсюда имя структуры.
Что унести
| операция | двоичная | биномиальная | Фибоначчи |
|---|---|---|---|
insert |
O(log n) |
O(log n), аморт. O(1) |
O(1) |
min |
O(1) |
O(log n) или O(1) с указателем |
O(1) |
extract_min |
O(log n) |
O(log n) |
аморт. O(log n) |
decrease_key |
O(log n) |
O(log n) |
аморт. O(1) |
merge |
O(n) |
O(log n) |
O(1) |
жёсткая форма → дешёвые константы, но дорогое слияние
слабая форма → дешёвое слияние и разрез, но указатели и промахи кеша
Дейкстра и Прим: двоичная куча даёт O((V+E)·log V), Фибоначчи - O(E + V·log V). Разница
видна только на ПЛОТНЫХ графах, где доминирует слагаемое с E; на разреженных её нет.
Амортизация здесь не украшение, а механизм: вставка в биномиальную кучу - буквально инкремент
двоичного счётчика; разрез в куче Фибоначчи оплачивается снятием пометки (потенциал Φ = t + 2m).
Оценка относится к последовательности операций, а не к каждой по отдельности.
Практика: куча Фибоначчи в прикладном коде редкость - её место в доказательствах границ. Где нужны
слияния, берут спаривающуюся или левостороннюю кучу; где нужен дешёвый decrease_key, обычно
хватает двоичной кучи с ленивым удалением.
И отдельный вывод, который часто важнее выбора структуры: прежде чем менять структуру, проверь
ПОРЯДОК операций. Слить k списков цепочкой - Θ(N·k), турниром - Θ(N·log k), и обе версии
используют одно и то же слияние.
Куда это ведёт
Следующая глава - непересекающиеся множества: ещё одна структура, которая умеет всего две операции и держит на себе алгоритм Крускала.
Комментарии
Пока нет комментариев. Будь первым!
Оставить комментарий