Парная КучаPairing Heap

Инвариант — обычный heap-order, но структура — не лес, а одно heap-ordered многодетное дерево: у каждого узла есть список детей (обычно реализуется как "первый ребёнок, следующий брат", left-child/right-sibling), и ключ родителя ≤ ключей всех детей. meld(a, b) — вся суть структуры: сравниваются корни a и b, тот, что с большим ключом, становится новым самым левым ребёнком того, что с меньшим ключом, и результат — новый корень с меньшим ключом. Ровно одно сравнение, O(1), без всяких условий на форму дерева. insert(key) — это meld текущей кучи с новым деревом из одного узла. find-min — чтение корня, O(1).The invariant is ordinary heap-order, but the structure isn't a forest — it's one heap-ordered multiway tree: every node has a list of children (usually implemented as "first child, next sibling"), and a parent's key ≤ all its children's keys. meld(a, b) is the entire essence of the structure: the roots a and b are compared, and whichever has the larger key becomes the new leftmost child of whichever has the smaller key, with the result being a new root holding the smaller key. Exactly one comparison, O(1), with no conditions on tree shape at all. insert(key) is just melding the current heap with a new singleton tree. find-min is reading the root, O(1).

extract-min — единственная нетривиальная операция, и она же дала структуре название. Корень удаляется, остаются его дети — список из нескольких поддеревьев. Их нужно объединить в одно дерево, и стандартный способ (two-pass pairing) — два прохода: первый проход разбивает список детей слева направо на пары и сливает (meld) каждую пару в одно дерево — получается примерно вдвое более короткий список; второй проход объединяет получившиеся деревья справа налево (последнее сливается с предпоследним, результат — с следующим слева, и так до конца) в одно финальное дерево, которое становится новым корнем. Именно парное объединение детей в первом проходе и дало название "парная куча". decrease-key(x, new_key) — уменьшить ключ узла x; если x не корень, вырезать поддерево x из-под родителя (O(1), просто перестройка указателей) и слить (meld) его обратно с корнем всей кучи, O(1) на само вырезание+meld — но амортизированная стоимость всей последовательности операций decrease-key строго не доказана: известна только вилка между Ω(log log n) и O(log n), что делает это одной из немногих не до конца решённых задач в теории структур данных.extract-min is the one non-trivial operation, and it's the one that gave the structure its name. The root is removed, leaving its children — a list of several subtrees. They need to be combined into one tree, and the standard approach (two-pass pairing) uses two passes: the first pass splits the child list left to right into pairs and melds each pair into one tree — yielding a list roughly half as long; the second pass combines the resulting trees right to left (the last one melds with the second-to-last, that result melds with the next one to the left, and so on to the end) into one final tree, which becomes the new root. It's precisely this pairwise combining of children in the first pass that gave the structure the name "pairing heap." decrease-key(x, new_key) decreases node x's key; if x isn't the root, x's subtree is cut from its parent (O(1), just a pointer rearrangement) and melded back with the whole heap's root, O(1) for the cut+meld itself — but the amortized cost of an entire sequence of decrease-key operations isn't strictly proven: only a gap between Ω(log log n) and O(log n) is known, making this one of the few not-fully-resolved problems in data-structure theory.

struct Node {
    int key;
    Node* child = nullptr;      // первый ребёнок// first child
    Node* sibling = nullptr;    // следующий брат// next sibling
    Node* parent = nullptr;
};

Node* meld(Node* a, Node* b) {          // вся суть структуры — O(1)// the entire essence of the structure — O(1)
    if (!a) return b;
    if (!b) return a;
    if (a->key > b->key) std::swap(a, b);
    b->sibling = a->child;               // b становится новым первым ребёнком a// b becomes a's new first child
    a->child = b;
    b->parent = a;
    return a;
}

Node* merge_pairs(Node* first) {         // two-pass pairing// two-pass pairing
    if (!first || !first->sibling) return first;
    Node* a = first, *b = first->sibling, *rest = b->sibling;
    a->sibling = b->sibling = nullptr;
    return meld(meld(a, b), merge_pairs(rest));  // pass 1 + pass 2 слиты рекурсией// pass 1 + pass 2 fused via recursion
}

Node* extract_min(Node* root) {
    Node* result = merge_pairs(root->child);
    delete root;
    return result;                     // новый корень (или nullptr, если куча опустела)// the new root (or nullptr if the heap became empty)
}

extract-min — самая показательная операция структуры. Демонстрация проигрывает оба прохода отдельно: сначала попарное слияние детей слева направо (первый проход), затем объединение получившихся деревьев справа налево (второй проход) в единый новый корень.extract-min is the structure's most illustrative operation. The demo auto-plays both passes separately: first the pairwise merge of children left to right (pass one), then combining the resulting trees right to left (pass two) into a single new root.

В отличие от кучи Фибоначчи, где амортизированный O(1) на decrease-key строго доказан через потенциальную функцию, для парной кучи такого доказательства нет. Известна нижняя граница Ω(log log n) (Фредман показал, что декремент ключа не может быть быстрее этого в определённой модели вычислений) и верхняя граница O(log n) — но точное амортизированное значение между ними остаётся открытым вопросом уже несколько десятилетий. Это редкий пример базовой структуры данных, широко используемой на практике, чья теоретическая сложность до конца не понята, — обычно бывает наоборот: сложность доказана, но структура не используется (как куча Фибоначчи).Unlike a Fibonacci heap, where amortized O(1) decrease-key is strictly proven via a potential function, no such proof exists for a pairing heap. A lower bound of Ω(log log n) is known (Fredman showed that a key decrement can't be faster than this in a certain computational model) and an upper bound of O(log n) — but the exact amortized value between them has remained an open question for decades. This is a rare example of a basic, widely-used-in-practice data structure whose theoretical complexity isn't fully understood — usually it's the other way around: the complexity is proven but the structure isn't used (as with the Fibonacci heap).