Min-Heap, step by step.

// how min-heaps work

How a min-heap works

What is a min-heap?

A min-heap is a binary heap: a complete binary tree in which every parent is less than or equal to its children, so the smallest value is always at the root. It is usually stored in an array rather than as linked nodes. Peek, also called find-min, reads the root without changing the heap, in O(1) time.

This page and the app use a min-heap throughout; the max-heap is the mirror image. The data structure is unrelated to heap memory.

The min-heap property: every parent is less than or equal to its children

The rule compares a parent only with its own children. The two children are not ordered, and nodes in different subtrees are not ordered at all. In the example, the root's children are 35 and 16, and under 16 the larger 93 comes first.

So a heap is not sorted: its largest value, 93, is on level 2, while the smaller 58 and 49 are a level lower. Equal values are allowed.

Min-heap as a complete binary tree: why the height is O(log n)

In a complete binary tree every level is full except possibly the last, which fills from the left. A complete tree of n nodes has height log₂ n rounded down (in edges, as on the binary search tree page): the ten-node example has height 3. Complete is not the same as full: 59 has one child.

Min-heap array representation: parent and child indices

Reading the tree level by level, left to right, gives the array. With no gaps, a node's index fixes its parent and children, so no pointers are stored. For the node at index i, counting from 0:

• parent: (i − 1) / 2, rounded down
• left child: 2i + 1
• right child: 2i + 2

In the figure, 35 at index 1 has its children at indices 3 and 4, and 91 at index 9 has its parent at (9 − 1) / 2 = 4. The root has no parent.

CLRS and many other textbooks count from 1: parent i / 2, children 2i and 2i + 1. This page and the app count from 0.

Min-heap insertion: sift up

A new value goes into the first free slot as a new leaf, which keeps the tree complete. Then it sifts up: while it is smaller than its parent, the two swap. It stops at a parent that is not larger, or at the root. Other names are bubble-up and percolate-up.

Here 5 goes to index 10, under 59. 5 < 59, so they swap; 5 < 35, so they swap again. The new parent 0 is smaller, so 5 stops at index 1: [0, 5, 16, 46, 35, 93, 36, 58, 49, 91, 59]. Step through it below.

Insert 5

All steps as text

1. The new value 5 goes into the first free slot, index 10: a new leaf below 59. Step forward to insert it.
2. Compare 5 with its parent 59 — the parent must be the smaller.
3. 5 and 59 are out of order — the min-heap property is violated.
4. Swap 5 and 59.
5. Compare 5 with its parent 35 — the parent must be the smaller.
6. 5 and 35 are out of order — the min-heap property is violated.
7. Swap 5 and 35.
8. Compare 5 with its parent 0 — the parent must be the smaller.
9. 5 is in the right place — the min-heap property holds.

Min-heap extract-min: sift down from the root

Extract-min swaps the root with the last leaf and removes the last slot, which now holds the minimum. The new root then sifts down: it is compared with its smaller child (the left one on a tie; the only child if there is one), and if that child is smaller, they swap. It stops when the value is not larger than its smaller child, or when it has no children. Other names are bubble-down and percolate-down.

Here 0 swaps with the last leaf 91 and is removed. 91 swaps with the smaller child 16 (35 vs 16), then with 36 (93 vs 36), and ends as a leaf at index 6: [16, 35, 36, 46, 59, 93, 91, 58, 49]. Step through it below.

Extract the minimum

All steps as text

1. The minimum is always at the root: 0. Step forward to extract it.
2. Swap the root with the last leaf.
3. Remove 0 — the extracted minimum.
4. 91 just moved to its new position — to check the heap is still valid, find its smaller child: 35 or 16.
5. Compare 91 with its smaller child 16 — the parent must be the smaller.
6. 91 and 16 are out of order — the min-heap property is violated.
7. Swap 91 and 16.
8. 91 just moved to its new position — to check the heap is still valid, find its smaller child: 93 or 36.
9. Compare 91 with its smaller child 36 — the parent must be the smaller.
10. 91 and 36 are out of order — the min-heap property is violated.
11. Swap 91 and 36. Since 91 has no children, no more comparisons are needed — the min-heap property is restored.

Deleting any node from a min-heap: sift up or down

Delete swaps the node with the last leaf and removes the last slot. If the replacement is smaller than its new parent, it sifts up; otherwise it sifts down.

Here 35, at index 1, swaps with the last leaf 91 and is removed. 91 is not smaller than its new parent 0, so it moves down: it swaps with the smaller child 46 (46 vs 59), then with 49 (58 vs 49), and ends as a leaf: [0, 46, 16, 49, 59, 93, 36, 58, 91]. Step through it below.

Delete 35

All steps as text

1. 35, at index 1, is selected for deletion. Step forward to delete it.
2. Swap the node with the last leaf.
3. Remove 35 — the deleted node.
4. 91 just moved to its new position — to check the heap is still valid, find its smaller child: 46 or 59.
5. Compare 91 with its smaller child 46 — the parent must be the smaller.
6. 91 and 46 are out of order — the min-heap property is violated.
7. Swap 91 and 46.
8. 91 just moved to its new position — to check the heap is still valid, find its smaller child: 58 or 49.
9. Compare 91 with its smaller child 49 — the parent must be the smaller.
10. 91 and 49 are out of order — the min-heap property is violated.
11. Swap 91 and 49. Since 91 has no children, no more comparisons are needed — the min-heap property is restored.

The replacement can move up only when the last leaf comes from another branch and is smaller than the new parent. In [1, 2, 50, 3, 4, 60, 70, 5], deleting 60 puts 5 under 50; 5 < 50, so they swap, giving [1, 2, 5, 3, 4, 50, 70].

Delete is O(log n) when the node's index is known; finding a value first is O(n). Some textbooks delete by decreasing the node's key below every other value, which sifts it to the root, and then running extract-min. This page and the app swap with the last leaf instead.

Build-heap (heapify): turning an array into a min-heap

Build-heap, Floyd's bottom-up method, reads an unordered array as a complete tree. Leaves are already heaps, so the pass starts at the last node with children, index n / 2 − 1 (rounded down; n / 2 with 1-based indices), and sifts down every node back to the root. By then both subtrees of a node are heaps, so one sift-down fixes it.

Here the array is reversed: [9, 8, 7, 5, 3, 2, 1]. The pass visits indices 2, 1 and 0. 7 swaps with its smaller child 1, and 8 with 3. The root 9 swaps with 1, then with 2. Four swaps give [1, 3, 2, 5, 8, 9, 7]. Step through it below.

Build-heap: Reversed array

All steps as text

1. An unordered array as a complete binary tree. Leaves have no children, so only the nodes above them need checking.
2. Take 7 to check.
3. Compare 7 with its smaller child 1 — the parent must be the smaller.
4. 7 and 1 are out of order — the min-heap property is violated.
5. Swap 7 and 1.
6. Take 8 to check.
7. Compare 8 with its smaller child 3 — the parent must be the smaller.
8. 8 and 3 are out of order — the min-heap property is violated.
9. Swap 8 and 3.
10. Take 9 to check.
11. Compare 9 with its smaller child 1 — the parent must be the smaller.
12. 9 and 1 are out of order — the min-heap property is violated.
13. Swap 9 and 1.
14. 9 just moved down a level. Check it against its children from here.
15. Compare 9 with its smaller child 2 — the parent must be the smaller.
16. 9 and 2 are out of order — the min-heap property is violated.
17. Swap 9 and 2.
18. Every node with children has now been checked, up to the root — the tree is a min-heap.

"Heapify" can mean one node's sift-down (MAX-HEAPIFY in CLRS, which uses max-heaps) or the whole build (Python's heapq.heapify). This page, like the app, says sift down and build-heap.

Why build-heap is O(n), not O(n log n)

A node sifts down at most as many levels as its height, and about half the nodes are leaves. In the 7-node tree the heights add up to 4 × 0 + 2 × 1 + 1 × 2 = 4, and the reversed array uses all four swaps.

Inserting the same values one by one costs up to each node's depth instead: 10 in total, and all ten swaps happen. Summed heights stay below n; summed depths grow like n log n.

Min-heap time complexity

Each sift follows one path between the root and a leaf, so it takes O(log n).

Operation	Time
Peek	O(1)
Insert	O(log n)
Extract-min	O(log n)
Delete, index known	O(log n)
Build-heap	O(n)
Search	O(n)

The heap takes O(n) space in one array, and every operation works in place.

Min-heap vs max-heap

A max-heap keeps the largest value at the root, with every comparison reversed; its sift-down swaps with the larger child. Python's heapq and Java's PriorityQueue are min-heaps by default. C++ std::priority_queue is a max-heap unless given std::greater.

Heap vs binary search tree

A binary search tree orders keys from left to right; a heap orders them only from top to bottom. A heap is always complete and needs no rotations, but finding a value takes O(n). For lookup by value or ordered traversal, a balanced tree such as a red-black tree fits better.

Where min-heaps are used: priority queues and more

• Priority queues: the heap is the standard implementation.
• Dijkstra's algorithm and A*: the node with the smallest tentative distance (for A*, distance plus estimated remaining distance) is taken next.
• Scheduling: the task with the highest priority or nearest deadline runs first.
• Top-k: a min-heap of size k keeps the k largest values seen so far.
• Heapsort: build a heap, then extract the root n times, in O(n log n). The app covers it in a separate Heap Sort topic.