Куча ФибоначчиFibonacci Heap

Инвариант остаётся heap-order (ключ родителя ≤ ключей детей), но деревья больше не обязаны быть биномиальными — их форма определяется историей операций. insert просто добавляет новый узел как отдельное дерево в список корней — O(1), без сравнений и связываний. union (merge) двух куч — это конкатенация двух списков корней и выбор нового минимума — тоже O(1). Вся структура "накапливает беспорядок" и разбирается только в момент extract-min: удаляется корень-минимум, его дети становятся новыми корнями, а затем идёт этап consolidate — деревья одинаковой степени (числа детей) связываются попарно, пока степени всех деревьев в списке корней не станут различны (тот же механизм, что merge в биномиальной куче, но выполняемый один раз за весь extract-min, а не при каждой вставке). Именно отложенная консолидация — источник амортизированной, а не строгой, сложности: одна отдельная операция extract-min может стоить дорого, если накопилось много деревьев, но в среднем по длинной последовательности операций она дешёвая.The invariant stays heap-order (a parent's key ≤ its children's keys), but the trees no longer have to be binomial — their shape is determined by the history of operations. insert simply adds the new node as a standalone tree to the root list — O(1), no comparisons or linking. union (merge) of two heaps is concatenating two root lists and picking the new minimum — also O(1). The whole structure "accumulates disorder" and only gets sorted out at extract-min: the minimum root is removed, its children become new roots, then a consolidate phase runs — trees of equal degree (child count) get linked pairwise until every tree in the root list has a distinct degree (the same mechanism as a binomial heap's merge, but run once per extract-min rather than on every insertion). This deferred consolidation is exactly the source of amortized, rather than strict, complexity: any single extract-min call can be expensive if a lot of trees have piled up, but averaged over a long sequence of operations it's cheap.

decrease-key(x, new_key) — самая интересная операция. Если после уменьшения ключ x всё ещё ≥ ключа его родителя, инвариант не нарушен, и делать больше ничего не нужно — O(1). Если инвариант нарушен (x стал меньше родителя), x вырезается (cut) из-под родителя и становится новым корнем — O(1). Но простое вырезание без ограничений позволило бы дереву терять детей бесконтрольно, что сломало бы амортизированный анализ (высота дерева перестала бы быть логарифмически связана с числом узлов). Решение — каждый узел хранит один бит "mark": true означает "этот узел уже потерял одного ребёнка с тех пор, как сам стал чьим-то ребёнком". Когда узел y теряет ребёнка через cut: если y ещё не помечен — просто помечается (первая потеря ребёнка прощается); если y уже был помечен — это его вторая потеря, и y тоже вырезается из-под своего родителя, становится корнем, снимает с себя метку, а её "получает" уже его родитель — проверка повторяется рекурсивно вверх (это и есть каскад). Корень никогда не помечается — маркировка касается только не-корневых узлов.decrease-key(x, new_key) is the most interesting operation. If after the decrease x's key is still ≥ its parent's key, the invariant isn't violated, and nothing further needs to happen — O(1). If the invariant is violated (x became smaller than its parent), x is cut from its parent and becomes a new root — O(1). But unrestricted cutting would let a tree lose children without limit, which would break the amortized analysis (the tree's height would stop being logarithmically bounded by its node count). The fix — every node stores one "mark" bit: true means "this node has already lost one child since it itself became someone's child." When a node y loses a child via a cut: if y isn't marked yet, it simply gets marked (the first lost child is forgiven); if y was already marked, this is its second loss, and y itself gets cut from its own parent, becomes a root, clears its own mark, and its parent then "inherits" the check — the check repeats recursively upward (this is the cascade). A root is never marked — marking only applies to non-root nodes.

struct Node {
    int key;
    Node* parent = nullptr;
    std::vector<Node*> children;
    bool mark = false;
};

void cut(Node* x, Node* y) {              // вырезать x из-под родителя y, сделать корнем// cut x from parent y, make it a root
    remove_from(y->children, x);
    x->parent = nullptr;
    x->mark = false;
    root_list.push_back(x);
}

void cascading_cut(Node* y) {
    Node* z = y->parent;
    if (!z) return;                    // y уже корень// y is already a root
    if (!y->mark) {
        y->mark = true;                // первая потеря — прощается// first loss — forgiven
    } else {
        cut(y, z);                        // вторая потеря — вырезаем и каскадируем// second loss — cut and cascade
        cascading_cut(z);
    }
}

void decrease_key(Node* x, int new_key) {
    x->key = new_key;
    Node* y = x->parent;
    if (y && x->key < y->key) {
        cut(x, y);
        cascading_cut(y);
    }
    if (x->key < min_node->key) min_node = x;
}

Дерево заранее устроено так, что один decrease-key вызывает каскад минимум в 2 уровня. Кнопка проигрывает шаги: вырезание узла, проверка метки родителя, вырезание родителя (если он уже был помечен), и так вверх до корня или до первого непомеченного предка.The tree is pre-arranged so that one decrease-key triggers a cascade at least 2 levels deep. The button auto-plays the steps: cutting the node, checking the parent's mark, cutting the parent too (if it was already marked), and so on up to the root or the first unmarked ancestor.

Куча Фибоначчи существует ради одного результата: с амортизированным O(1) decrease-key и O(log n) extract-min, алгоритмы Дейкстры и Прима достигают теоретической границы O(E + V log V) — без такого decrease-key граница была бы O(E log V). Это делает кучу Фибоначчи важной для асимптотической теории алгоритмов. Но на практике она почти не используется: константы велики (много отдельно аллоцированных узлов, указатели parent/child/sibling, битовые метки), локальность кэша плохая (узлы разбросаны по памяти, в отличие от плотного массива бинарной кучи), а реализация — с каскадными вырезаниями, консолидацией по степеням — заметно сложнее и более подвержена ошибкам. Для большинства реальных размеров входа (до миллионов элементов) простая бинарная или d-арная куча оказывается быстрее в реальном времени выполнения, несмотря на худшую асимптотику decrease-key. Многие практические реализации выбирают вместо кучи Фибоначчи парную кучу (2.3.3.5) — она проще в реализации и эмпирически быстрее, даже не имея доказанной O(1) границы на decrease-key.A Fibonacci heap exists for one result: with amortized O(1) decrease-key and O(log n) extract-min, Dijkstra's and Prim's algorithms reach the theoretical bound O(E + V log V) — without such a decrease-key the bound would be O(E log V). That makes the Fibonacci heap important for the asymptotic theory of algorithms. But in practice it's almost never used: the constants are large (many separately allocated nodes, parent/child/sibling pointers, mark bits), cache locality is poor (nodes are scattered across memory, unlike a binary heap's dense array), and the implementation — with cascading cuts, degree-based consolidation — is noticeably more complex and error-prone. For most real-world input sizes (up to millions of elements), a plain binary or d-ary heap turns out faster in wall-clock time, despite decrease-key's worse asymptotics. Many practical implementations reach for a pairing heap (2.3.3.5) instead of a Fibonacci heap — it's simpler to implement and empirically faster, even without a proven O(1) bound on decrease-key.