A min-heap is 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. Stored in an array, it reads the minimum in O(1) time, and an insertion or an extract-min takes O(log n). This page explains how it works, with step-by-step animations of insertion, extract-min, deletion and build-heap from the VisiGrab app.
// how min-heaps work
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 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.
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 log2 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.
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 links are stored. For the node at index i, counting from 0:
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.
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.
In the player, 5 goes in as a new leaf under 59 and sifts up past 59 and 35, stopping below the root 0: [0, 5, 16, 46, 35, 93, 36, 58, 49, 91, 59].
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.
In the player, the root 0 swaps with the last leaf 91 and is removed, and 91 sifts down past 16 and 36 to end as a leaf: [16, 35, 36, 46, 59, 93, 91, 58, 49].
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.
In the player, 35 at index 1 swaps with the last leaf 91 and is removed. 91 is not smaller than its new parent 0, so it sifts down past 46 and 49: [0, 46, 16, 49, 59, 93, 36, 58, 91].
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, 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.
In the player, the reversed array [9, 8, 7, 5, 3, 2, 1] becomes [1, 3, 2, 5, 8, 9, 7] after sift-downs at indices 2, 1 and 0, four swaps in all.
"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.
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.
It swaps the root, the minimum, with the last leaf, drops the last slot and sifts the new root down, in O(log n); the extract-min section and its player show each step.
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.
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.
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.
O(n log n). The app covers it in a separate Heap Sort topic.The full source code is on GitHub, in Python, Java and C++.
// in the app
In VisiGrab you build the heap yourself, and every change plays out step by step.
Insert any value with “+”, extract the minimum with “MIN”, tap a node to delete it, or start from a random heap.
Step through every comparison and swap, and step back through them.
Two more arrays to turn into a heap step by step: “Almost a heap” and “Deep sift”.
A topic of its own shows how a heap sorts an array.
A min-heap implementation with insert, extract-min and delete, explained part by part.
Check what you have learned before moving on.
// build your own
Download VisiGrab and step through every insertion, extraction and deletion yourself.
The min-heap is one of 30+ topics. See them all