Биномиальная КучаBinomial Heap

Биномиальное дерево порядка 0 — это один узел. Дерево порядка k получается связыванием (link) двух деревьев порядка k-1: корень с большим ключом становится самым левым (или любым новым) ребёнком корня с меньшим ключом — операция O(1), потому что меняется только один указатель. Отсюда: order-k дерево имеет ровно 2^k узлов, высоту k, и корень с k детьми, которые сами являются корнями деревьев порядков k-1, k-2, ..., 0. Биномиальная куча — это лес таких деревьев, не более одного на каждый порядок: если у кучи n элементов, набор присутствующих порядков — это в точности позиции единичных битов в двоичной записи n. Например, n=13=1101₂ означает лес из деревьев порядков 3, 2 и 0 (8+4+1=13).An order-0 binomial tree is a single node. An order-k tree is formed by linking (link) two order-(k-1) trees: the root with the larger key becomes the leftmost (or any new) child of the root with the smaller key — an O(1) operation, since only one pointer changes. From this: an order-k tree has exactly 2^k nodes, height k, and a root with k children that are themselves the roots of order k-1, k-2, ..., 0 trees. A binomial heap is a forest of such trees, at most one per order: if the heap has n elements, the set of orders present exactly matches the positions of the set bits in n's binary representation. For example, n=13=1101₂ means a forest of order-3, order-2, and order-0 trees (8+4+1=13).

Слияние (union/merge) двух биномиальных куч — это буквально сложение в столбик в двоичной системе. Списки деревьев обеих куч, отсортированные по возрастанию порядка, "складываются" как цифры числа: если на позиции k есть только одно дерево — оно остаётся как есть (бит без переноса); если два дерева одного порядка k — они связываются (link) в одно дерево порядка k+1, это "перенос" в следующий разряд; если попадаются три дерева порядка k одновременно (два своих плюс перенос) — одно остаётся на месте, два других связываются и переносятся дальше, — та же логика, что при сложении двух чисел в столбик, где в одном разряде может встретиться до трёх единиц (два слагаемых плюс перенос). Каждое связывание — O(1), разрядов не больше O(log n), поэтому весь merge — O(log n). Извлечение минимума: минимум — это корень с наименьшим ключом среди корней всех деревьев леса (просмотр всех корней — O(log n), потому что деревьев не больше log n). После удаления минимума его k детей (сами являющиеся корнями деревьев порядков k-1..0) образуют новый биномиальный лес, который сливается обратно с оставшимся лесом той же процедурой merge.Merging (union) two binomial heaps is literally long-form binary addition. The two heaps' tree lists, sorted by ascending order, "add up" like the digits of a number: if position k has only one tree, it stays as-is (a bit with no carry); if there are two trees of the same order k, they're linked into one order-(k+1) tree — a "carry" into the next digit; if three order-k trees appear at once (two of your own plus an incoming carry), one stays put and the other two get linked and carried forward — the same logic as adding two numbers in columns, where a single digit can see up to three ones (two addends plus a carry). Each link is O(1), there are at most O(log n) digits, so the whole merge is O(log n). Extracting the minimum: the minimum is the root with the smallest key among all the forest's roots (scanning all roots is O(log n), since there are at most log n trees). After removing the minimum, its k children (themselves the roots of order k-1..0 trees) form a new binomial forest, which gets merged back into the remaining forest via the same merge procedure.

struct Node {
    int key, order = 0;
    std::vector<Node*> children;
};

Node* link(Node* a, Node* b) {           // оба порядка k -> один порядка k+1// both order k -> one of order k+1
    if (a->key > b->key) std::swap(a, b);
    a->children.push_back(b);
    a->order++;
    return a;
}

// merge — слияние двух списков корней, отсортированных по order, с переносом// merge — combining two root lists sorted by order, with carrying
std::vector<Node*> merge(std::vector<Node*> h1, std::vector<Node*> h2) {
    auto combined = merge_sorted_by_order(h1, h2);  // как слияние в mergesort// like the merge step in mergesort
    std::vector<Node*> result;
    for (size_t i = 0; i < combined.size(); ) {
        Node* cur = combined[i];
        if (i + 1 < combined.size() && combined[i+1]->order == cur->order) {
            // перенос: связываем два дерева одного порядка// carry: link two same-order trees
            Node* linked = link(cur, combined[i+1]);
            combined[i+1] = linked;             // протолкнуть перенос дальше по списку// push the carry further down the list
            i += 1;
        } else {
            result.push_back(cur);
            i += 1;
        }
    }
    return result;
}

Две небольшие биномиальные кучи показаны как леса деревьев с подписанным порядком каждого. merge проигрывает шаги "сложения с переносом" — совпавшие порядки подсвечиваются и связываются в дерево следующего порядка. extract-min находит минимальный корень, отделяет его детей как новый лес и сливает его с оставшимся.Two small binomial heaps are shown as forests of trees, each labeled with its order. merge auto-plays the "addition with carry" steps — matching orders are highlighted and linked into a tree of the next order. extract-min finds the minimum root, splits off its children as a new forest, and merges it back with what remains.

Биномиальная куча даёт строгий (не амортизированный) O(log n) на insert, extract-min и merge — уже намного лучше, чем O(n) на merge у бинарной кучи. Но insert через биномиальную кучу технически реализуется как "слить с кучей из одного элемента" — то есть тоже платит за возможные каскадные переносы: в худшем случае O(log n), хотя в среднем (амортизированно) O(1), потому что переносы, как и при обычном инкременте двоичного счётчика, происходят редко. Куча Фибоначчи и парная куча (следующие две статьи) идут дальше именно в этом месте: они делают merge/insert "ленивым" — не выполняют связывание немедленно, а откладывают его до следующего extract-min, добиваясь строго O(1) амортизированного insert вместо O(log n) в худшем случае.A binomial heap gives a strict (non-amortized) O(log n) for insert, extract-min, and merge — already far better than a binary heap's O(n) merge. But insert via a binomial heap is technically implemented as "merge with a singleton heap" — so it too pays for possible cascading carries: O(log n) in the worst case, though O(1) on average (amortized), because carries, just like in an ordinary binary counter increment, happen rarely. A Fibonacci heap and a pairing heap (the next two articles) push further exactly here: they make merge/insert "lazy" — they don't perform the linking immediately, deferring it until the next extract-min, achieving a strict amortized O(1) insert instead of O(log n) worst case.