Skip to content

Pairing / Leftist Heap Hot Sheet

Use this sheet when the missing operation is:

meld two heaps

not predecessor, rank, or split-by-key.

Do Not Use When

Choose By Signal

  • every item starts as one heap, then heaps keep unioning -> Pairing Heap / Leftist Heap
  • one active ordered set with neighbor queries -> set / multiset
  • one global best candidate only -> plain priority_queue
  • persistent branching versions -> Persistent Treap hot sheet

Core Invariants

  • leftist heap: heap order plus rank(left) >= rank(right) so merge only walks one short right spine
  • pairing heap: heap order plus two-pass pairing of root children after delete-min
  • owner lookup is often a separate DSU-style layer, not part of the heap invariant itself
  • equal keys should usually be tie-broken by item id if future operations still reference item ids

Main Traps

  • forgetting to reject operations on deleted items
  • trying to solve meldable-heap tasks with repeated element moves
  • not separating "which heap contains x" from "who is x's parent in the heap tree"
  • overclaiming generic decrease-key / arbitrary erase support when the template does not expose them

Exact Starter Route

Reopen Paths