Overview
A leftist heap stores a heap-ordered binary tree with a null-path-length invariant. Merge recursively combines right spines and swaps children when needed so the right spine stays short.
CoreSource checked
Leftist Heap
Maintains a mergeable heap by keeping the shortest null path on the right spine.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Priority Queues
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
meldable priority queuepriority queuesheap orderdata structures
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(log n)
Worst
O(n)
Space
O(n)
When to Use
- Use when meld is important and a simple binary-tree heap is preferred.
- Use when logarithmic right-spine length gives acceptable performance.
When Not to Use
- Avoid when array locality of a binary heap is more important than meld.
- Avoid if null-path metadata is hard to maintain safely.
What It Does
- Maintains heap order and null-path lengths
- Melds heaps by merging right spines
- Swaps children to preserve the leftist invariant
Use Cases
- Mergeable priority queues
- Workloads with frequent heap meld operations
- Teaching structural invariants in pointer-based heaps
Inputs
- Keys, values, items, or graph records
- Operations such as insert, delete, or query
Outputs
- Stored structure state
- Query result or updated collection
Pseudocode
- 1.If either heap is empty, return the other heap
- 2.Make the smaller root the new root
- 3.Merge the larger-root heap into the new root's right child
- 4.Swap children if the left null-path length is smaller than the right
- 5.Update the root's null-path length and return it
Canonical Example
- Input
- meld heap rooted at 2 with heap rooted at 5
- Output
- heap rooted at 2 with right spine repaired by null-path lengths
- Explanation
- The smaller root remains the root, and the merged child order is adjusted to keep the right spine short.
Implementation Notes
- Define null-path length consistently for null children.
- Implement all updates through the meld operation.
- Test merges where one heap is empty and where root order changes.
Common Pitfalls
- Forgetting to update null-path length after merge corrupts future operations.
- Swapping children before comparing null-path lengths can break the invariant.
- Recursive merge depth should be considered for very large heaps.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow maintaining a null-path-length invariant to merge heaps quickly on a small meldable priority queue example.
Step 1 of 5: If either heap is empty, return the other heap
data-structures-mechanismNotes
Leftist heaps trade array locality for a simple and efficient meld operation.
Sources (1)
What each reference supports for this entry.
Handbook of Data Structures and Applications
BookData-structures reference for Leftist Heap null-path length ordering and meldable heap operations.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toSkew Heap
Leftist heaps store null-path metadata, while skew heaps use self-adjusting swaps.
Alternative toBinomial Heap
Both support melding, but maintain different structural invariants.
Variant ofHeap
A leftist heap is a pointer-based priority queue with heap order.
Related Algorithms
Tags
Data StructurePriority Queue