Heaps
A tree that lives inside an arrayA heap always keeps the smallest (min-heap) or largest (max-heap) value at the top, so you can get it in O(1) and remove it in O(log n). It is a complete binary tree, but it is stored in a plain array — the small number on each node is its array index.
- Min-heapevery parent ≤ its children
- Stored asan array: children of i are 2i+1, 2i+2
- Usepriority queues, heap sort
- Comparing
- Swapping
- New / done
- Removed
- 3array index of the node
Ready
Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode
Every operation, in plain steps
These are exactly the steps the visualizer animates.
A tree without pointers
A heap is a COMPLETE binary tree: every level is full except maybe the last, which fills from the left. That means it fits in an array with no gaps and needs no pointers — the position of a value tells you where its parent and children are.
int heap[CAPACITY];
int size = 0;
// for the value at index i:
int parent(int i) { return (i - 1) / 2; }
int left(int i) { return 2 * i + 1; }
int right(int i) { return 2 * i + 2; }
// min-heap rule: heap[parent(i)] <= heap[i]
The heap rule
- Min-heap: every parent ≤ its children.
- Max-heap: every parent ≥ its children.
- So the root is the minimum (or maximum).
- Siblings are NOT in any order — it is not a BST.
Insert (sift up)
- Put the value in the first free spot (end of the array).
- Compare it with its parent.
- If it should be above the parent, swap.
- Repeat until it fits or reaches the root.
Extract (sift down)
- Remember the root — it is returned.
- Move the LAST value into the root.
- Swap it with its better child while it is out of order.
- The tree stays complete: no gaps.
Build a heap in O(n)
- Start from the last parent: index n/2 − 1.
- Sift each parent down, moving towards the root.
- Most nodes are near the bottom and move very little.
- Total work is O(n), not O(n log n).
Priority queue
- A queue where the most important item leaves first.
- Insert = heap insert, O(log n).
- Serve next = extract root, O(log n).
- Used in hospital triage, CPU scheduling, Dijkstra's algorithm.
Heap sort
- Build a max-heap from the array.
- Swap the root (maximum) to the end.
- Shrink the heap by one and sift down.
- See it step by step on the Sorting page.
Pseudocode
Language-independent steps. The visualizer shows the same logic in C, Python and Java.
How fast is each operation?
n = number of values. The height of a heap is always ⌊log₂ n⌋ because the tree is complete, so sift-up and sift-down take at most O(log n) swaps.
| Operation | Best | Average | Worst | Speed |
|---|---|---|---|---|
| Peek (min / max) | O(1) |
O(1) |
O(1) |
Instant |
| Insert | O(1) |
O(log n) |
O(log n) |
Grows with n |
| Extract min / max | O(log n) |
O(log n) |
O(log n) |
Grows with n |
| Build heap (bottom-up) | O(n) |
O(n) |
O(n) |
Grows with n |
| Search for any value | O(1) |
O(n) |
O(n) |
Grows with n |
Heap vs BST vs sorted array
| Heap | Balanced BST | Sorted array | |
|---|---|---|---|
| Get the minimum | O(1) | O(log n) | O(1) |
| Remove the minimum | O(log n) | O(log n) | O(n) — shift everything |
| Insert | O(log n) | O(log n) | O(n) |
| Find any value | O(n) | O(log n) | O(log n) |
| Memory | Just an array | Nodes + pointers | Just an array |
Array positions for index i
| Relation | Formula | Example (i = 4) |
|---|---|---|
| Parent | (i − 1) / 2 | 1 |
| Left child | 2i + 1 | 9 |
| Right child | 2i + 2 | 10 |
| Last parent | n / 2 − 1 | n = 10 → 4 |
Check your understanding
Answer each question — you will see the explanation straight away.
In a min-heap, where is the smallest value?
Every parent is ≤ its children, so the smallest value must be at the top: index 0.
The value at index 5 of a heap array: what is the index of its parent?
parent(i) = (i − 1) / 2 = (5 − 1) / 2 = 2.
Where does a newly inserted value go first?
It goes into the first free spot so the tree stays complete, then it sifts up.
After extracting the root, which value is moved into the root position?
Moving the last value keeps the array without gaps; then it sifts down to its place.
Is [3, 5, 4, 9, 6, 8] a valid min-heap?
3 ≤ 5, 4; 5 ≤ 9, 6; 4 ≤ 8. Every parent is ≤ its children. A heap does not need to be sorted.
How long does it take to build a heap from n values with bottom-up heapify?
Most nodes are near the bottom and sift down only a little; the total work adds up to O(n).
Heaps quiz
Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.