A binary heap keeps one inequality true — every parent is at most its children — on a complete tree stored in a plain array. That is enough for insert and extract-min in O(log n), with no pointers anywhere, because the tree’s shape is arithmetic on indices. What it is not is sorted: siblings are in no particular order, and the array almost never reads as an ordered list.
Core ideas
Three things, and the third is the one that gets misread on every first reading: the inequality, the layout, and what the inequality does not say.
parent ≤ child at every node. Nothing relates a node to its sibling, to its cousin, or to anything that is not on the path between it and the root. The consequence that matters is that the minimum is at the root, because the root is an ancestor of everything — and the consequence that gets assumed and is false is that the array is in order.
A complete tree can be laid out level by level in an array, and then the children of position i are at 2i and 2i + 1 when positions start at 1. No node stores a link; the tree is a way of reading the array. This is why a heap is the cheapest structure in this course to implement and the one a sorting algorithm can build in place.
Insert puts the new key at the end and swaps it up while it is smaller than its parent: at most one comparison per level. Extract-min moves the last key to the root and swaps it down while it is larger than a child: two comparisons per level, because the smaller child has to be found first. A complete tree on n nodes has height ⌊log₂ n⌋, and that is the whole bound.
The material
What a heap promises, how an array becomes a tree, and the measured comparison counts against the height.
A min-heap is a complete binary tree whose every node satisfies the heap property: the key at a node is less than or equal to the keys at both of its children. Complete means every level is full except possibly the last, which is filled from the left.
The root therefore holds a minimum, since it is an ancestor of every node and the property is transitive along a path. A max-heap reverses the inequality and nothing else about it changes.
Completeness is what allows the array layout, and the array layout is what removes the pointers. Write the levels out in order, left to right. Then for a position i counted from 1, the children sit at 2i and 2i + 1 and the parent at ⌊i/2⌋. The lab draws its array with positions counted from 0, where the same tree has its children at 2i + 1 and 2i + 2 — the arithmetic differs by where you start counting and the tree is identical, which is worth confirming once on the picture rather than believing.
That array is what the lab holds after inserting 1, 9, 2, 8, 3, 7, 4, 6 in that order, and it is a perfectly valid heap. It is also not sorted, not nearly sorted, and not sorted after any prefix: the second element is 3 and the third is 2. If a heap were sorted then building one would sort, and sorting costs more than building a heap does — which is the argument that ought to make the misconception uncomfortable before the picture does.
Put the new key in the first free array position, which keeps the tree complete. Then while it is smaller than its parent, swap the two. The property can only be violated between the new key and its ancestors, and each swap repairs one level, so the walk stops at the root at the latest: at most ⌊log₂ n⌋ comparisons and as many swaps.
Inserting 8 into the three-element heap the lab has after 1, 9, 2 compares 8 against its parent 9, swaps, compares against 1, and stops: 2 comparisons, 1 swap, against a bound of ⌊log₂ 4⌋ = 2. Inserting 7 a step later costs 1 comparison and no swap at all, because it lands under 2 and is bigger. Both are O(log n); one of them did nothing.
The root is the answer. Removing it leaves a hole, so move the last element into the root — which keeps the tree complete — and then push it down: compare its two children with each other, then compare it with the smaller one, and swap if it is larger. Two comparisons per level, ⌊log₂ n⌋ levels, so at most 2⌊log₂ n⌋.
Four comparisons against a bound of four: the sift reached a leaf, which is the worst case at that size, and the counter and the bound agree. That agreement is a coincidence of this input, and the very next extraction in the lab also costs 4 while the inserts before it cost between 0 and 2 against bounds of 0 to 3. Over the whole ten-operation sequence the lab counts 18 comparisons and 7 swaps, and reports that every single step came in at or under its bound.
That last report is the one to be careful with. “Every step came in under its bound” is a statement about ten operations on eight keys. The bound itself is a statement about a path in a complete tree, and the proof is one line: a complete tree on n nodes has height ⌊log₂ n⌋, a sift visits each level at most once, and each level costs at most two comparisons. The lab can show you the walk; it cannot show you that there is no taller tree.
Interactive
Comparisons per operation against the height of the tree
Method
Four steps, and the first is the one that prevents an hour of confusion: decide where you are counting positions from.
From 1, children of i are at 2i and 2i + 1. From 0, they are at 2i + 1 and 2i + 2. Both are in use, the lab draws the second, and an index formula from one convention applied under the other silently walks to the wrong node.
The new key goes in the first free position so the tree stays complete. Compare it with its parent and swap while it is smaller. Stop at the root or at the first parent that is already smaller — there is nothing further up to fix.
Take the root as the answer, move the last element into the root, and push it down. At each level find the smaller child first, then compare. Skipping the child-versus-child comparison is the error that produces a tree that still looks plausible.
Walk every node and confirm parent ≤ children. Then compare the comparisons you made with ⌊log₂ n⌋ for an insert and 2⌊log₂ n⌋ for an extract. A count above the bound means a step went wrong; a count well below it means the sift stopped early, which is ordinary.
The lab’s opening sequence, by hand. The comparison count and the bound sit in the last two columns; the array after each step is what the picture is drawing.
Look at the array after the eighth insert: 1 3 2 6 8 7 4 9. Every root-to-leaf path increases — 1 3 6 9, 1 3 8, 1 2 7, 1 2 4 — and the array itself is in no order whatever. 3 precedes 2, and 8 precedes 7 and 4. This is the picture that settles the misconception, and it is worth staring at until it stops looking like a mistake.
The two extractions both cost 4, which equals 2⌊log₂ 7⌋ and 2⌊log₂ 6⌋. Both sifts went all the way to a leaf, which is the worst case at those sizes. The inserts, by contrast, came in at 0 to 2 against bounds of 0 to 3, because a sift up stops as soon as the parent is smaller and most keys arrive somewhere they can stay.
For a faded rehearsal, insert 8, 7, 6, 5, 4, 3, 2, 1 in that order and extract three times. The supplied observation is that every one of these keys is smaller than everything already in the heap, so every insert sifts all the way to the root: the swap count and the comparison count coincide. Predict the total before running it — the lab reports 22 comparisons and 17 swaps — and then say why reversing the input made no difference at all to the bound.
You should be able to insert and extract by hand on a drawn heap without losing completeness, find the smaller child before comparing, convert between the array and the tree in both index conventions, and quote the comparison bound for each operation with the reason the extraction’s bound carries a factor of two.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.