Биномиальная куча: двоичная запись числа как структура

Если ты можешь построить B_k из двух B_{k−1}, объяснить соответствие «лес деревьев ↔ двоичная запись n» и провести слияние как сложение с переносом, листай до «Теперь сам».

Как думаешь, какой формы должны быть деревья

Прошлый урок показал: дешёвое слияние требует леса деревьев, а быстрый поиск минимума - чтобы деревьев было мало, O(log n). Прежде чем читать дальше, подумай, какие размеры деревьев дают такую гарантию САМИ СОБОЙ, без дополнительной работы. Подсказка: сколько деревьев понадобится, если разрешены любые размеры? А если только степени двойки, и каждого размера не больше одного?

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

Гирьки для весов номиналом 1, 2, 4, 8, 16 - по одной каждого номинала. Любой вес до 31 набирается единственным способом, и гирек всегда не больше пяти: это и есть двоичная запись числа. Сложить два набора - значит сложить два числа: две гирьки по 4 заменяются одной на 8, и так дальше по разрядам. Никакого пересчёта содержимого, только работа с номиналами - их мало, и их ровно логарифм.

Механизм: дерево B_k, лес и сложение с переносом

B₀ = один узел

B_k = два дерева B_(k−1): корень одного становится ребёнком корня другого
      (ребёнком делают того, у кого КЛЮЧ ХУЖЕ - тогда свойство кучи сохраняется)

свойства B_k:  узлов 2^k,  высота k,  у корня k детей,
               на глубине d ровно C(k, d) узлов   ← биномиальные коэффициенты

откуда это: при склейке корень одного B_(k−1) становится ЕЩЁ ОДНИМ ребёнком
корня другого, значит детей было k−1, стало k (и дети корня B_k - это готовые
B_(k−1), B_(k−2), ..., B₀). А узлы глубины d в новом дереве - это узлы глубины d
старого плюс узлы глубины d−1 подвешенного: C(k−1, d) + C(k−1, d−1) = C(k, d),
правило треугольника Паскаля

Куча из n элементов - набор деревьев B_k с РАЗНЫМИ k, по одному на каждую единицу в двоичной записи n. Размер записан в самой структуре: n = 13 = 1101₂ даёт B₃ + B₂ + B₀, и деревьев ровно три - столько, сколько единиц. Больше ⌊log₂ n⌋ + 1 деревьев не бывает никогда.

слияние(A, B):
    идём по разрядам k = 0, 1, 2, ...
    в разряде k может оказаться до трёх деревьев B_k: из A, из B и перенос
    два из них соединяем в одно B_(k+1) - это ПЕРЕНОС в старший разряд
    оставшееся (если есть) остаётся в разряде k

Это сложение столбиком, где цифра - дерево. Разрядов O(log n), в каждом константная работа, значит слияние - O(log n).

Остальные операции выражаются через слияние:

вставка       : слить кучу с кучей из одного узла (B₀)      O(log n), амортизированно O(1)
минимум       : перебрать корни (их O(log n))               O(log n), или O(1) с указателем
извлечь мин.  : убрать корень дерева B_k; его k детей -
                это готовые B_(k−1) ... B₀, то есть куча;
                слить её с остатком                         O(log n)
уменьшить ключ: просеять узел вверх внутри своего дерева    O(log n)
                (как и в двоичной куче, узел надо ЗНАТЬ: лес на указателях
                 возвращает при вставке хендл на узел, и его хранят снаружи -
                 позиции здесь не индексы массива, а сами узлы)

Правило

B_k - два B_{k−1}, сцепленных корнями: 2^k узлов, высота k, k детей у корня, C(k, d) узлов на глубине d. Биномиальная куча - лес деревьев разных размеров, по одному на единицу в двоичной записи n, значит деревьев не больше ⌊log₂ n⌋ + 1. Слияние - сложение двоичных чисел с переносом: два B_k дают один B_{k+1} (ребёнком становится корень с худшим ключом). Все операции - O(log n), вставка амортизированно O(1).

Разбор: сливаем кучи на 5 и на 3 элемента

Куча A на 5 элементов: 5 = 101₂, значит деревья B₂ и B₀. Куча B на 3: 3 = 11₂, значит B₁ и B₀. Складываем 101₂ + 11₂ столбиком, и параллельно - деревьями.

1. Разряд 0: у A есть B₀, у B есть B₀ - два дерева одного размера. Соединяем их в B₁ (ребёнком делаем корень с худшим ключом) и отправляем ПЕРЕНОСОМ в разряд 1. В разряде 0 не остаётся ничего. В арифметике: 1 + 1 = 0 и перенос.
2. Разряд 1: у A ничего, у B есть B₁, пришёл перенос B₁ - снова два дерева. Соединяем в B₂, переносим в разряд 2. В разряде 1 пусто. В арифметике: 0 + 1 + 1 = 0 и перенос.
3. Разряд 2: у A есть B₂, пришёл перенос B₂ - два дерева. Соединяем в B₃, переносим. Разряд 2 пуст. В арифметике: 1 + 0 + 1 = 0 и перенос.
4. Разряд 3: только перенос B₃ - он и остаётся. В арифметике: 1.

Итог: одно дерево B₃ на 8 элементов, и 101₂ + 11₂ = 1000₂ = 8. Проверь: 5 + 3 = 8, сошлось. Работы - четыре разряда, то есть O(log n), и ни один элемент, кроме соединяемых корней, не был тронут. Сравни с двоичной кучей, где то же слияние потребовало бы переложить все восемь.

Разбор: почему вставка амортизированно O(1)

Вставка - это слияние с B₀, то есть прибавление единицы к двоичному числу. Если младшие разряды заняты, пойдёт цепочка переносов: 0111₂ + 1 = 1000₂ - три соединения. Значит худший случай вставки - Θ(log n). Но такие вставки редки, и это тот самый случай, который в разделе про амортизацию разбирался на двоичном счётчике: разряд k переключается раз в 2^k инкрементов, поэтому суммарное число переключений за m инкрементов - m·(1 + 1/2 + 1/4 + ...) < 2m, то есть в среднем меньше двух на операцию. Ровно то же и здесь: m вставок в биномиальную кучу делают меньше 2m соединений деревьев, значит амортизированная цена вставки - O(1).

Оговорка, без которой вывод был бы неверным: амортизированная оценка относится к ПОСЛЕДОВАТЕЛЬНОСТИ вставок, а не к отдельной вставке. Если чередовать вставку и извлечение минимума в худшей точке, каждая отдельная операция может стоить log n. Амортизация обещает сумму, а не каждое слагаемое, - это различие стоит держать в голове всюду, где встречается слово «амортизированно».

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

Первое: подвешивать при соединении не тот корень. Ребёнком становится корень с ХУДШИМ ключом (в min-куче - с большим); наоборот - и свойство кучи нарушается в самом корне. Второе: допустить два дерева одинакового размера и не соединить их - число деревьев перестанет быть O(log n), а поиск минимума деградирует. Третье: после извлечения минимума забыть, что дети снятого корня идут в ОБРАТНОМ порядке степеней (B_{k−1}, ..., B₀) и образуют готовую кучу, - их не нужно разбирать по элементам, только слить с остатком. Четвёртое: считать биномиальную кучу быстрее двоичной по константам - она медленнее на обычных операциях (указатели, разбросанная память), и выигрыш даёт только слияние. Пятое: брать её ради decrease_key - он здесь O(log n), ровно как у двоичной; дешёвого уменьшения ключа даёт только следующий урок.

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

Биномиальная куча - редкий гость в прикладном коде, и честно сказать об этом полезнее, чем рассказывать про мнимую распространённость: там, где нужны слияния, чаще берут спаривающиеся (pairing) или левосторонние (leftist) кучи - у них проще код и лучше константы. Ценность этого урока в другом. Во-первых, это чистейший образец приёма «структура повторяет запись числа»: то же соответствие между двоичным представлением и набором блоков лежит в основе динамизации структур данных (приём Бентли-Сакса), скип-листов, систем счисления в персистентных структурах. Увидев его один раз, начинаешь узнавать. Во-вторых, биномиальная куча - обязательная ступень к куче Фибоначчи: та получается из неё заменой «наводить порядок сразу» на «наводить порядок лениво», и без понимания первой вторая выглядит магией. В-третьих, связь «амортизация = двоичный счётчик» здесь видна как нигде: структура буквально считает.

Теперь сам

Биномиальная куча содержит 11 элементов. Какие деревья в ней лежат и сколько их? Что произойдёт при вставке одного элемента - сколько соединений сделает слияние?