Leftist Heap

Why it matters

Leftist heaps enable efficient merge. Understanding shapes functional PQ.

The architecture

Binary tree with s-value (null path length).

Left child's s-value >= right's.

Merge along right spine.

How it works end to end

Merge: recursively merge right spines.

Insert = merge with singleton.

Extract-min = merge children.

All ops O(log n).