Step by step
The example above, written out — the same steps the animation plays.
- 1An empty min-heap. A min-heap keeps the smallest value at the top: every parent is ≤ its children. It is stored as a plain array — children of i sit at 2i+1 and 2i+2.
- 2Insert 7. 7 goes in the next free spot (the end of the array).
- 3Insert 3. 3 goes in the next free spot (the end of the array).
- 43 vs parent 7. 3 < 7: swap up.
- 5Sift up. 3 moves up a level.
- 6Insert 9. 9 goes in the next free spot (the end of the array).
- 79 vs parent 3. 9 ≥ 3: heap order holds — stop.
- 8Insert 1. 1 goes in the next free spot (the end of the array).
- 91 vs parent 7. 1 < 7: swap up.
- 10Sift up. 1 moves up a level.
- 111 vs parent 3. 1 < 3: swap up.
- 12Sift up. 1 moves up a level.
- 13Insert 5. 5 goes in the next free spot (the end of the array).
- 145 vs parent 3. 5 ≥ 3: heap order holds — stop.
…and 14 more steps — press Play above to watch them all.
What's happening?
- Insert adds the value at the end, then swaps it up while it is smaller than its parent.
- Extract-min takes the top, moves the last value to the top, then swaps it down with its smaller child.
- The children of position i live at 2i+1 and 2i+2 — no pointers needed.
Complexity
- Time
- O(log n) insert and extract-min · O(1) to look at the minimum
- Space
- O(n)
Where you'll meet it
Priority queues: task schedulers, Dijkstra's shortest path, "top K" problems, merging sorted streams, and heap sort.
Common mistake
Expecting the array to be sorted. A heap only guarantees each parent ≤ its children — siblings can be in any order.
FAQ
Heap vs binary search tree?
A heap only knows where the smallest value is; a BST keeps everything in order. Heaps are simpler and faster for "give me the minimum".
Why store a tree in an array?
A heap is always a complete tree, so positions map neatly to indexes — it is compact and cache-friendly.
What is a max-heap?
The same with the order flipped: the largest value is at the top.