Pairing Heap — Interactive Visualization

Insert some values to begin. The heap is a multiway tree; the root is always the minimum.

A pairing heap is a self-adjusting heap represented as a multiway tree. - insert: O(1) — meld a singleton with the root. - find-min: O(1) — the root. - meld: O(1) — the smaller root becomes parent of the larger. - extract-min: amortized O(log n) — two-pass merge over the root's children. - decrease-key: amortized o(log n) (open problem); cut the subtree and meld it with the root.

Pass 1: walk children left-to-right, pairing consecutive ones — meld(c0,c1), meld(c2,c3), ... Pass 2: walk the resulting list right-to-left, melding each into an accumulator. The final accumulator becomes the new root.