Heaps
Heaps
Priority-ordered complete trees behind priority queues and heap sort.
Min-Heap
▶ viz
A complete binary tree stored in an array where every parent is ≤ its children, so the minimum is always at the root.
O(n) search · O(n) space
Max-Heap
▶ viz
A complete binary tree in array form where every parent is ≥ its children, so the maximum is always at the root.
O(n) search · O(n) space
Binary Heap
▶ viz
The array-encoded complete binary tree behind min-heaps and max-heaps: parent/child indices are computed, not stored.
O(n) search · O(n) space
Fibonacci Heap
A collection of heap-ordered trees with lazy consolidation giving amortized O(1) insert, merge, and decrease-key, and O(log n) extract-min.
O(n) search · O(n) space