Algorithms and data structures · Introductory

Binary heaps: repeatedly extracting the smallest value

Trace insertion, removal and bottom-up construction in an array heap, distinguishing ordering, shape, lookup costs and stable priorities.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Maintain shape and order separately
  2. Represent the complete tree with an array
  3. Insert at the end and move upward
  4. Fill the removed root with the last item
  5. Why bottom-up construction is linear
  6. Handle changed and tied priorities explicitly
  7. Check properties as well as a single trace
  8. Ask Logeia about this articleCheck your understanding

Maintain shape and order separately

A min binary heap has two independent invariants. Its shape is a complete binary tree: every level except possibly the last is full, and the last fills from left to right. Its order requires each parent to be no greater than its children. Following parent links proves that the root is no greater than any stored value. Neither sibling order nor the relative order of whole left and right subtrees is specified. The array [1,5,2,9,7,4] is therefore a valid min heap without being sorted. Do not apply the left-versus-right range rule of a binary search tree to a heap. Fast access to the minimum and sorted access to every item are different promises.

Represent the complete tree with an array

Using zero-based indices, node i has children at 2i+1 and 2i+2. A nonroot node has parent floor((i−1)/2). A child index outside the array denotes an absent child. Completeness makes this representation compact because parent-child relationships can be reconstructed without storing links at every node. The index formulas describe tree placement; they do not compute an arbitrary value’s location from its key. Boundary handling remains essential. Reading the minimum of an empty array, asking for the root’s parent, or following a nonexistent child must be handled explicitly. State whether the interface raises an error or uses another empty result, rather than allowing an accidental out-of-range access to define the behavior.

Insert at the end and move upward

Insert one into [2,5,4,9,7]. Appending gives [2,5,4,9,7,1], preserving the required shape. The new node’s parent is four at index two, so exchange those values. Its next parent is the root two; another exchange yields [1,5,2,9,7,4]. Only the path from the appended node toward the root needs repair because the other branches have not changed. That path has logarithmic height, giving O(log n) comparisons and moves in the heap operation. A dynamically growing backing array can additionally require reallocation on a particular insertion. Keep that storage-growth cost separate from the heap-order analysis, especially when reporting a strict worst-case latency guarantee for the whole container operation.

Python
import heapq
h = [2, 5, 4, 9, 7]
heapq.heappush(h, 1)
assert h == [1, 5, 2, 9, 7, 4]
assert heapq.heappop(h) == 1
assert h == [2, 5, 4, 9, 7]
assert all(h[(i - 1) // 2] <= h[i] for i in range(1, len(h)))

Fill the removed root with the last item

To remove one from [1,5,2,9,7,4], move the final four to the root and shorten the array, producing [4,5,2,9,7]. Of the root’s children five and two, choose the smaller two for the exchange. The result is [2,5,4,9,7]. Choosing the larger child can leave the parent greater than the other child and fail to restore the invariant. Continue downward only while a smaller child exists. The final item is chosen to preserve completeness, not because its value is close to the minimum. Merely inspecting the root is O(1); removing it and repairing order is O(log n). An interface promising a fast minimum lookup does not thereby promise constant-time deletion.

Why bottom-up construction is linear

Inserting n items one at a time gives a straightforward O(n log n) upper bound. Building directly from an existing array permits a different strategy. Leaves already form valid heaps, so repair each parent downward, starting at the last parent and working toward the root. There are many low nodes that move only a short distance, while the potentially expensive nodes near the root are few. The count of nodes at height roughly h decreases geometrically, so the total work can be bounded by a constant times n multiplied by a convergent sum of h/2^h. This gives O(n) construction. Charging every node the full tree height is a valid but loose bound that misses this important distinction.

Handle changed and tied priorities explicitly

A basic heap does not efficiently locate an arbitrary key merely because its minimum is easy to find. Updating a particular item can use an ID-to-index map that is maintained whenever items exchange positions. Another design adds a new candidate and discards stale candidates when they are later removed. That approach needs a memory policy because outdated candidates can remain stored for some time. Stable handling of equal priorities is another separate requirement. Comparing pairs of priority and insertion sequence preserves arrival order among ties, while still allowing a lower-priority-number item to precede an earlier arrival. Ensure that the sequence type has an adequate range and that comparison does not unexpectedly fall through to application objects that cannot be ordered.

Check properties as well as a single trace

After each operation, check that every existing child is no smaller than its parent. Also remove all inserted values and verify that the resulting sequence is sorted and preserves both multiplicity and item count. Empty, one-item, equal-value, increasing and decreasing inputs exercise different boundaries. Values that do not obey an ordinary total ordering, such as floating-point NaN under standard comparisons, need an explicit comparison policy. Passing the heap invariant does not establish safe concurrent access either; that requires the container’s synchronization contract. These checks validate ordering and preservation separately rather than treating a plausible root value from one example as proof that every internal element is correct or that every supported operation respects its advertised cost.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 9

Choose a learning path