Heap Variants

Heap-Based Data Structures

Type	Description	Key Characteristic	Typical Use Case	Access Pattern	Memory Behavior	Notes
Heap	Priority-based tree	Heap property	Priority queues	Root access	Tree-based	General concept
Binary Heap	Binary tree heap	Array-backed	Schedulers	Logarithmic	Contiguous	Most common
Min-Max Heap	Supports min and max	Alternating levels	Double-ended PQ	Logarithmic	Contiguous	Min & max in O(1)
D-ary Heap	Each node has d children	Shallower tree	High branching	Logarithmic	Contiguous	Fewer comparisons
Ternary Heap	3-ary heap	Reduced height	Priority queues	Logarithmic	Contiguous	D-ary variant
B-Heap	Memory-efficient heap	Block-based layout	Cache optimization	Logarithmic	Semi-contiguous	Improves locality
Weak Heap	Relaxed heap	Fewer comparisons	Sorting	Logarithmic	Contiguous	Efficient heap sort
Binomial Heap	Forest of trees	Fast merge	Meldable PQs	Logarithmic	Node-based	Supports union
Fibonacci Heap	Lazy consolidation	Amortized O(1) insert	Graph algorithms	Amortized log	Node-based	Complex but powerful
AF-Heap	Fibonacci variant	Simpler structure	Research	Amortized log	Node-based	Less overhead
Leonardo Heap	Used in smoothsort	Adaptive sorting	Sorting algorithms	Logarithmic	Contiguous	Data-order sensitive
2–3 Heap	Heap with 2–3 nodes	Balanced heap	Theoretical models	Logarithmic	Node-based	Rarely used
Soft Heap	Allows errors	Approximate keys	Approx algorithms	Amortized log	Node-based	Controlled corruption
Pairing Heap	Self-adjusting heap	Simple meld	Priority queues	Amortized log	Node-based	Practical alternative
Leftist Heap	Skewed structure	Fast merge	Meldable heaps	Logarithmic	Node-based	Left-heavy
Skew Heap	Self-adjusting	No balance info	Meld-heavy systems	Amortized log	Node-based	Simpler than leftist
Treap	Heap + BST	Randomized priority	Ordered sets	Expected log	Node-based	Dual properties
Beap	Bi-parental heap	Efficient search	Priority search	Logarithmic	Contiguous	2D structure
Brodal Queue	Optimal PQ	Worst-case optimal	Theoretical CS	O(1) ops	Node-based	Extremely complex