Heaps: a nearly-sorted tree in an array
A heap is a binary tree with one promise: every parent is smaller than its children (in a min-heap), so the minimum always sits at the root, ready in O(1). The surprise is that the tree is never actually built — no nodes, no pointers. A heap is an ordinary array, and the tree exists only in the arithmetic of the indices: multiply or divide by two with a binary shift and you walk from any element to its parent or children. This page builds that idea up piece by piece, then runs the three operations that maintain it — heapify, insert, and extract-min — live, step by step.
The one-sentence idea. Store a complete binary tree level by level in an array. Because the tree is complete, the children of index i are always at 2i + 1 and 2i + 2 and the parent is one right-shift away — so “rebalancing” is just swapping an element up or down a single root-to-leaf path, never touching the rest of the array.
1 — What a heap is: a complete tree with one ordering rule
Two properties define a binary heap, and they are independent. Shape: the tree is complete — every level is fully filled except possibly the last, which fills left to right with no gaps. Order (min-heap): every parent is less than or equal to both of its children. Note what the order property does not say: nothing relates a node to its siblings, its cousins, or its grandchildren beyond the chain of parents. A heap is only partially ordered — it is not sorted, and it is not a binary search tree. That weakness is exactly what makes it cheap to maintain.
| Heap-order property (min-heap) | |
|---|---|
| Max-heap | Flip every comparison: each parent is greater than or equal to its children and the root is the maximum. Everything on this page works identically with the comparisons reversed; the examples use a min-heap throughout. |
Figure 1: A valid min-heap of 9 elements: tree above, the same heap as an array below
Figure 1. Click any node (or any array cell) and its family lights up in both views at once. Read the array left to right, top level first: it is the tree, flattened. The heap [1, 3, 2, 5, 4, 8, 6, 9, 7] is not sorted (3 sits before 2), yet every parent is smaller than its children, which is all the structure a priority queue needs.
How to read this
- The root, index 0, holds 1, the minimum of all nine values, guaranteed by the order property applied transitively down every path.
- Completeness is what makes the array trick possible: with no gaps, “the next node” is always just “the next index”.
- A sorted array is a valid heap, but most heaps are not sorted — the heap gives up total order to buy O(log n) updates.
2 — The array embedding: parents and children by binary shift
Number the tree positions in level order starting at 0, and store position i at A[i]. Then the family of any node is pure arithmetic. Doubling an index moves one level down, halving moves one level up — and doubling and halving integers is precisely what the binary shift operators do: << 1 appends a 0 bit (×2), >> 1 drops the last bit (⌊÷2⌋). In the cleaner 1-indexed convention (root at A[1], slot 0 wasted) the formulas are exact shifts with no corrections: parent is i >> 1, children are i << 1 and (i << 1) + 1. With the usual 0-indexed array the same shifts appear with +1 and −1 adjustments, shown in the table.
| Left child of | |
|---|---|
| Right child of | |
| Parent of |
Why the shift works is visible in binary. An index in binary is a path: read the bits after the leading 1 from the root, 0 for “go left”, 1 for “go right”. Appending a bit (shifting left) walks one step down; dropping the last bit (shifting right) walks one step up. The explorer below does the arithmetic live — drag the index and watch the bits, the family, and the tree all move together.
Figure 2: Index explorer: node i = 6 in a 15-element heap
Figure 2. The values in this tree are the indices themselves, so the arithmetic is the picture: the children of 6 are 13 and 14 because 6 in binary is 110, shifting left gives 1100 (12), and adding 1 and 2 gives 1101 (13) and 1110 (14). Going up, (13 − 1) ≫ 1 drops 1100 back to 110, which is node 6 again.
No pointers, no allocation, perfect locality. A pointer-based tree spends memory on two child pointers per node and scatters nodes across the heap (the memory kind). The array form stores n values and nothing else, and a sift walks a path whose elements sit at doubling — cache-friendly — strides. This is why essentially every production heap (C++ std::priority_queue, Java PriorityQueue, Python heapq) is an array underneath.
3 — The midpoint: where the parents end and the leaves begin
In a complete tree of n nodes, exactly the first ⌊n/2⌋ indices have children; the rest are leaves. The boundary — the midpoint of the array — is the last index that is a parent. One right shift finds it:
| Last parent (the midpoint) | |
|---|---|
| Leaf test | A leaf is trivially a valid one-element heap — there is nothing below it that it could violate. That single fact is what makes the O(n) build in Step 4 possible. |
Figure 3: n = 15 elements: midpoint at index 6, 7 parents and 8 leaves
Figure 3. Half the array — roughly — is leaves. For n = 15 the split is 7 parents to 8 leaves, and it stays near half for every n: a complete tree packs about as many leaves as internal nodes. Heapify only has work to do on the left half; every leaf is already a correct heap of size one.
4 — Heapify: building a heap in place, from the midpoint down
Given an arbitrary array, the naive build inserts elements one at a time: O(n log n). Floyd’s heapify is smarter and does it in place, in O(n). The idea follows directly from Step 3: leaves are already heaps, so start at the midpoint — the last parent — and work backwards to the root, sifting down each element: compare it with its smaller child and swap if the child is smaller, then keep sifting from the child’s position until the element is no larger than both children, or reaches a leaf. Going bottom-up guarantees that when index i is processed, both of its subtrees are already valid heaps, so one sift-down makes the whole subtree rooted at i valid. When the root finishes, the array is a heap.
heapify(A): // in place, O(n) n = A.length // start at the midpoint for i = (n >> 1) - 1 down to 0: siftDown(A, n, i) siftDown(A, n, i): loop: l = (i << 1) + 1 r = l + 1 smallest = i if l < n and A[l] < A[smallest]: smallest = l if r < n and A[r] < A[smallest]: smallest = r if smallest == i: break swap A[i], A[smallest] i = smallest
Figure 4: Heapify step 0 of 10
Figure 4. The unsorted array [9, 4, 7, 1, 8, 3, 6, 2, 5] has n = 9, so the midpoint is (9 ≫ 1) − 1 = 3. Step through it: index 3 (value 1) is already fine, index 2 swaps once, index 1 sinks two levels, and the root 9 sinks three levels to a leaf — six swaps total, and notice that roughly half the swaps happen at the bottom of the tree, where paths are short. That asymmetry is the whole O(n) argument, below.
Why bottom-up is O(n), not O(n log n). Most nodes sit near the leaves, where a sift-down has almost nowhere to go: half the nodes sift 0 levels, a quarter sift at most 1, an eighth at most 2. Summing swaps over all nodes: n/2 × 0 + n/4 × 1 + n/8 × 2 + …, converges to at most n swaps in total. Building by repeated insertion pays a full log n climb for the large elements near the leaves instead, which is where the extra log factor comes from.
5 — Insert: append at the end, then sift up
Adding an element must preserve completeness, and there is exactly one slot that does: the next free position at the end of the array, A[n], the leftmost gap on the last level. Placed there, the new element can break the order property in only one way: it may be smaller than its parent. So sift up: while the element is smaller than its parent (found with one right shift, (i − 1) ≫ 1), swap them, and repeat from the parent’s position. The element climbs at most one root-to-leaf path, so insert is O(log n), and the rest of the heap is never touched. This is precisely a targeted rebalance: the damage from an insertion is confined to a single path, and sift-up is the repair walk along it.
push(A, x): // O(log n) A.append(x) i = A.length - 1 // sift up, parent(i) = (i - 1) >> 1 while i > 0 and A[parent(i)] > A[i]: swap A[i], A[parent(i)] i = parent(i)
Figure 5: Insert step 0 of 4: ready to insert
Figure 5. Choose a value below and step through its insertion into the heap [1, 3, 2, 5, 4, 8, 6]. The default, 0, is smaller than everything, so it climbs all three levels to the root. Try 4 instead: it swaps once with 5 and stops under 3: sift-up ends the moment the parent is no larger, often well before the root.
6 — Extract-min: take the root, move the last element up, sift down
Reading the minimum is O(1): it is A[0]. Removing it is the interesting part. Deleting the root outright would split the tree, so instead: save A[0], move the last element A[n − 1] into the root slot, shrink the heap by one, and repair. The moved element is almost surely too big for the root, but it can only violate order against its children — so sift down, exactly the repair used by heapify: swap with the smaller child (choosing the smaller child is essential — swapping with the larger one would put that larger child above the smaller one and break their order), repeating until the element settles. One path down, O(log n), and the heap is whole again with the new minimum at the root.
popMin(A): // O(log n) top = A[0] // last element moves to the root A[0] = A.pop() if A not empty: siftDown(A, A.length, 0) return top
Figure 6: Extract-min: ready
Figure 6. Extract from [1, 3, 2, 5, 4, 8, 6, 9, 7]: the 1 leaves, the last element 7 takes the root, then sifts down swapping with 2 and then 6, leaving [2, 3, 6, 5, 4, 8, 7, 9]. Keep extracting — the minima come out in sorted order, which is exactly how heapsort works: heapify an array once, then repeatedly extract the minimum (in practice in place, from the back, to sort descending with a max-heap).
7 — Rebalancing: when it is needed, and why it is always one path
A heap never needs the global rebalancing a search tree does — there is no rotation, no re-coloring, no restructuring pass. The order property can only break locally, along the single path touched by a change, and each operation repairs exactly that path. The complete list of triggers:
| What changed | What can break | Repair |
|---|---|---|
| Element appended (insert) | New element may be smaller than its parent | Sift up from the last index: swap with parent while smaller |
| Root removed (extract-min) | Last element, moved to the root, may be larger than a child | Sift down from index 0: swap with the smaller child while larger |
| A key decreases (priority raised) | Element may now be smaller than its parent | Sift up from that index: the core of Dijkstra’s decrease-key |
| A key increases (priority lowered) | Element may now be larger than a child | Sift down from that index |
| Arbitrary array, or many keys changed | Order may be violated everywhere | Heapify from the midpoint: rebuild in O(n) rather than repairing pair by pair |
The direction rule is the whole decision procedure: an element that got smaller (or arrived from below) can only be wrong against its parent, so it can only need to go up; an element that got larger (or arrived from above) can only be wrong against its children, so it can only need to go down. Try all of it in the playground: insert and extract animate their repair paths, decreasing or increasing a selected element triggers the matching sift, and “Shuffle” breaks the heap so you can watch heapify restore it from the midpoint.
Figure 7: Playground heap: valid min-heap, n = 7
Figure 7. A free heap to experiment on. The status line under the controls checks the heap property across the whole array after every operation — shuffle the values and it names the first violating parent-child pair; heapify and it goes green again.
The one caveat: arbitrary deletion and decrease-key need a map
- Sift-up after a key change is O(log n) if you know the index. Finding an arbitrary element in a heap is O(n) (heaps are not searchable), so real priority queues keep a side table from element to current index and update it on every swap.
- Deleting an arbitrary element combines both repairs: overwrite it with the last element, then sift up or down depending on how the replacement compares with its new parent and children.
8 — Costs at a glance, and where heaps earn their keep
| Operation | Cost | Why |
|---|---|---|
Peek minimum, A[0] | O(1) | The minimum is the root by definition |
| Insert (push) | O(log n) | Append, then sift up one path of height ⌊log₂ n⌋ |
| Extract-min (pop) | O(log n) | Move last to root, sift down one path |
| Decrease / increase key | O(log n) | One sift, up or down, from the element’s index |
| Build (heapify) | O(n) | Bottom-up sift-downs from the midpoint; most paths are short |
| Search for a value | O(n) | No ordering between subtrees to prune by — the heap’s one real weakness |
| Extra memory | O(1) | In place in the array; no pointers, no node objects |
That cost profile — cheapest possible access to the extremum, logarithmic updates, linear build, zero overhead — makes the heap the default engine wherever work is consumed in priority order: operating-system and event-loop schedulers, Dijkstra’s and A* shortest paths (with decrease-key), Huffman coding, streaming medians with paired min- and max-heaps, top-k queries, and heapsort, which is just heapify followed by n extract-mins for an O(n log n) sort with O(1) extra space. Whenever a problem asks for “the smallest (or largest) thing, repeatedly, while new things keep arriving”, it is asking for a heap — and underneath, it is asking for an array, two shifts, and a midpoint.
Heap Data Structure: a visual explainer. All diagrams are drawn live from the arrays they show; every animation step is computed by the same sift-up, sift-down and heapify code printed on this page.