Heap Visualization

Solid edges = left children (heavier side). Dashed edges = right spine (kept short by leftist property).

Complexity

Key Properties

• •Min-heap order — every parent ≤ its children
• •Leftist property — npl(left) ≥ npl(right) at every node
• •Short right spine — guaranteed O(log n) length; merge stays on the right
• •All operations via merge — insert and extract-min both reduce to merge
• •Not balanced — the tree is intentionally skewed leftward; that's the design

Applications

• •Mergeable priority queues — when frequent heap merging is needed
• •Event simulation — merging event queues from parallel processes
• •Persistent data structures — functional style; easy to share structure
• •Teaching — elegant example of merge-first design; simpler than Fibonacci heaps

Active Recall Quiz