Watch insert, extract, and build heap in action!
Min-Heap: Parent ≤ Children
Parent
⌊(i − 1) / 2⌋Left Child
2 × i + 1Right Child
2 × i + 2👆 Click any node in the tree to see the formulas in action
Array Representation:
Start from index ⌊n/2⌋ − 1 = 2 and bubble down each node going left to index 0. Leaves (indices 3–6) are already valid heaps — skip them!
| Operation | Time | Space | Why |
|---|---|---|---|
| Insert | O(log n) | O(1) | Bubble up through at most log n levels |
| Extract Min | O(log n) | O(1) | Bubble down through at most log n levels |
| Peek (min) | O(1) | O(1) | Min is always at index 0 (root) |
| Heapify (build) | O(n) | O(1) | Bottom-up — most nodes are leaves and don't move |
| Insert n items | O(n log n) | O(n) | Each of n inserts costs O(log n) |
| Search | O(n) | O(1) | Heap is not sorted — must check every element |
Heapify works bottom-up: it calls bubble_down from the last non-leaf to the root. Most nodes are near the bottom of the tree and move very little:
Leaves (bottom)
n/2 nodes
0 moves
Level above
n/4 nodes
≤ 1 move
Next level
n/8 nodes
≤ 2 moves
Root (top)
1 node
≤ log n moves
Total work: n/4 · 1 + n/8 · 2 + n/16 · 3 + ... ≈ n (geometric series). Half the nodes do zero work, a quarter do one swap — it adds up to O(n), not O(n log n).