{ }
</>
[ ]
!=
#

Heap Architect

Heap Data Structures

From standard Binary Heaps to theoretical structures like Fibonacci and Soft Heaps.

Binary Heap

Standard

Complete binary tree where parent ≥ child (Max) or parent ≤ child (Min).

Insert: O(log n)
Extract: O(log n)

B-Heap

Systems

Binary heap implemented on pages of virtual memory. Optimized to reduce cache misses.

Key for: Large databases, External Memory.

d-ary Heap

Generalization

Generalization where nodes have d children instead of 2. Reduces tree height.

Decr-Key: O(log_d n)
Extract: O(d log_d n)

Binomial Heap

Mergeable

A collection of Binomial Trees. Supports fast merging of two heaps.

Meld: O(log n)
Structure: Forest of trees $B_k$.

Fibonacci Heap

Theoretical

Collection of trees with lazy operations. Critical for Dijkstra's Algorithm optimization.

Decr-Key: O(1) amortized
Meld: O(1)

Leftist Heap

Mergeable

Binary tree that maintains a "null path length" property (leftist). Optimized for melding.

Meld: O(log n)

Skew Heap

Self-Adjusting

Simplified Leftist Heap. No path length storage. Always swaps children during merge.

Amortized O(log n) for all operations.

Pairing Heap

Practical

Simple to implement and practically fast. Multi-ary tree structure with multipass merge.

Complexity analysis is still an open math problem.

Weak Heap

Optimization

Relaxed structure (some nodes don't enforce heap property) to reduce comparisons.

Soft Heap

Approximate

Allows "corruption" (error) in values for speed. Used in optimal MST algorithms.