6.1 Binary heaps and priority queues

A priority queue answers a different question from an ordinary queue. An ordinary queue asks which item arrived first; a priority queue asks which available item has the most urgent key. The binary heap is a compact way to answer that question while keeping insertion and removal efficient. Its speed comes from two invariants that do different jobs: one controls the shape of the tree, and the other controls the order of its keys.

This note uses min heaps and a one-based array, matching the course lecture. Every operation will be analysed through the same discipline:

1. identify which invariant an update might break;
2. change only one root-to-leaf or leaf-to-root path;
3. stop only when both invariants hold again.

Motivation

Algorithms such as Prim's and Dijkstra's repeatedly need the smallest current candidate. Scanning an unsorted collection can make insertion cheap, but every minimum removal then scans the whole collection. Keeping a collection fully sorted makes the minimum easy to locate, but insertion may shift many items. A heap deliberately maintains less information than a sorted array. It knows enough to expose the minimum and to repair an update along one short path, but it does not try to determine the complete sorted order.

That trade-off is exactly what a priority queue needs. An item may contain a key together with a payload, such as (tentative distance, vertex). The key decides priority; the payload is the object returned with it. In this note the examples display only integer keys so that the structural argument remains visible.

The distinction between the abstraction and its implementation matters. A caller should ask for the smallest-priority item without depending on where it is stored. The heap implementation, meanwhile, is free to rearrange items after every update. This is why an intermediate heap array should not be used as though it were a sorted report. To obtain all keys in increasing order, one must repeatedly remove the minimum, paying for each repair; merely reading the array from left to right does not have that meaning.

Definitions

Definition

Minimum priority queue

A minimum priority queue is an abstract data type whose core operations are insert(x), which adds an item with key x, find_min(), which reads an item of minimum key, and delete_min(), which removes and returns an item of minimum key. The abstraction specifies behaviour, not representation. A binary min heap is one implementation of it.

Definition

Complete binary tree

A binary tree is complete when every level except possibly the last is full, and the last level is occupied from left to right with no gap. This is a shape condition only; it says nothing about the values stored at the nodes.

This unit follows Chapter 4's node-count height convention: h is the number of nodes on a longest root-to-leaf path. Thus an empty tree has height 0 and a one-node tree has height 1. Depth still counts edges from the root, so the root has depth zero. For a nonempty complete tree with n nodes, h = floor(log_2 n) + 1; equivalently, 2^{h-1} ≤ n ≤ 2^h - 1. A root-to-leaf repair traverses at most h - 1 = floor(log_2 n) vertical edges, which is why one such repair takes O(log n) time.

Definition

Min-heap order

A binary tree satisfies min-heap order when every non-root node has a key greater than or equal to the key of its parent. Equivalently, every parent is less than or equal to each of its children. A binary min heap is a complete binary tree that satisfies min-heap order.

Heap order is a partial order, not a sorted traversal order. Two siblings need not be ordered relative to one another, and a node in the left subtree need not be smaller than a node in the right subtree. Equal keys are permitted. Unless an implementation adds a separate tie-breaker, the heap also makes no promise that equal-priority items leave in arrival order.

Definition

One-based array representation

Store the complete tree level by level in A[1..n]. For a node at index i,

$$\operatorname{parent}(i)=\left\lfloor\frac{i}{2}\right\rfloor, \qquad \operatorname{left}(i)=2i, \qquad \operatorname{right}(i)=2i+1.$$

The parent formula applies when i>1; a child exists only when its index is at most n. The internal nodes are exactly indices 1 through floor(n/2), so the remaining indices are leaves.

Completeness is what makes these formulas possible. Appending at A[n+1] adds the next legal last-level position, and removing A[n] removes the last legal position. No pointers or explicit child links are required.

The array formulas also expose two useful boundary tests. A node is a leaf exactly when its left-child index exceeds the current size. A node has two children exactly when its right-child index is at most the current size; otherwise an existing left child is its only child. Keeping these tests explicit prevents an algorithm from reading beyond the active heap. The array's allocated capacity may exceed the current size, but cells beyond the size are not members of the heap and must never participate in comparisons.

Theorems

Theorem

Root-minimum invariant and find-min cost

In a nonempty min heap, the root A[1] contains a globally minimum key. Therefore find_min takes O(1) time once emptiness has been checked.

Theorem

Single-path repair bound

Insertion repaired by sift-up and minimum deletion repaired by sift-down each take O(log n) worst-case time in a binary heap of n items. Both operations preserve completeness and min-heap order.

Theorem

Bottom-up build-heap bound

If n keys are first placed in complete-tree array order and sift_down is run at indices floor(n/2), floor(n/2)-1, ..., 1, the resulting array is a min heap and the total worst-case running time is O(n).

The last result is stronger than multiplying n/2 calls by the maximum downward-edge count of the whole tree. Most calls start near the leaves and cannot descend far. The analysis must charge each node only for the downward edges available in its own subtree.

Proof sketch or proof idea

For the root-minimum result, take any node v. The unique path from the root to v is nondecreasing because every parent key is at most its child key. Consequently the root key is at most the key at v. Since v was arbitrary, the root is globally minimum. Reading A[1] does not depend on n, so the operation is constant-time. Notice what the proof does not claim: the second-smallest key need not be at a predetermined array index.

Insertion and sift-up

To insert x, first create a hole at index n+1. This preserves completeness but may violate heap order between the hole and its ancestors. While the parent key is greater than x, move that parent down into the hole and move the hole to the parent's index. Then place x in the final hole.

INSERT(A, n, x):
    n := n + 1
    i := n
    while i > 1 and A[floor(i / 2)] > x:
        A[i] := A[floor(i / 2)]
        i := floor(i / 2)
    A[i] := x
    return n

Only the new node's ancestor chain can be wrong: all other parent-child relations are unchanged. Every moved parent was already no larger than its other child, and the loop stops exactly when the new parent is no larger than x or the root is reached. If the tree has node-count height h, the hole moves upward through at most h - 1 = floor(log_2 n) edges, which is O(log n).

A useful loop invariant makes the argument precise. Before each comparison, every edge not incident to the hole satisfies heap order, and placing x in the hole is the only unresolved possibility. If the parent is too large, moving that parent down fixes the lower position and transfers the unresolved edge one level upward. If the comparison succeeds, inserting x fixes the last unresolved edge. The algorithm cannot cycle because the hole's depth strictly decreases on every iteration.

Delete-min and sift-down

Removing the root directly would leave a gap at the wrong end of the complete tree. Save the minimum, remove the last key last, and regard the root as a hole. Repeatedly move the smaller child into that hole while last is larger than that child. Finally place last in the stopping position.

DELETE_MIN(A, n):
    if n = 0: report underflow
    minimum := A[1]
    if n = 1: return (minimum, 0)
    last := A[n]
    n := n - 1
    i := 1
    while 2 * i ≤ n:
        child := 2 * i
        if child + 1 ≤ n and A[child + 1] is smaller than A[child]:
            child := child + 1
        if last ≤ A[child]: break
        A[i] := A[child]
        i := child
    A[i] := last
    return (minimum, n)

Choosing the smaller child is essential. Moving the larger child up could immediately place it above a smaller sibling and break heap order. As with insertion, relations outside one path never change. The hole descends through at most h - 1 = floor(log_2 n) vertical edges, giving O(log n) worst-case time.

Here the loop invariant is slightly different: both subtrees below the hole are already heaps, and all edges outside the hole path are valid. If last is no greater than the smaller child, then it is no greater than either child and may safely fill the hole. Otherwise the smaller child is the only safe one to promote. The unresolved position moves strictly downward, so termination is again guaranteed by the finite height. Removing the last array cell before this repair is what preserves the shape invariant throughout.

Bottom-up construction

Leaves already satisfy heap order because they have no children. Process the internal nodes in reverse array order:

BUILD_HEAP(A, n):
    for i := floor(n / 2) downto 1:
        SIFT_DOWN(A, n, i)

When index i is processed, both child subtrees have larger indices and have already been heapified. SIFT_DOWN therefore repairs the subtree rooted at i without damaging either child heap. Reverse induction on i proves that after the loop, the subtree at index 1—the entire array—is a heap.

For running time, let d be the maximum number of downward edges from a node to a leaf in its subtree. A node with downward-edge capacity d can descend at most d edges, and a complete tree has O(n/2^{d+1}) such nodes. Hence the total work is bounded by

$$O\!\left( n\sum_{d\ge 0}\frac{d}{2^{d+1}} \right)=O(n),$$

because the convergent downward-edge-weighted series is a constant (equivalently, sum_{d>=0} d/2^d = 2). This is why bottom-up construction is linear even though one individual sift-down can be logarithmic. Building by n successive insertions has the weaker worst-case bound O(n log n).

There are therefore two legitimate construction strategies with different worst-case accounting. Repeated insertion maintains a valid heap after every new key; this is useful when items arrive online, but the total of the possible path lengths is logarithmic per arrival. Bottom-up construction assumes all keys are already available. It first obtains the complete shape for free from their array positions, then repairs subtrees from smaller to larger d. The final root call can traverse all h - 1 downward edges, but there is only one such root; the large population of nodes lies near the leaves and contributes little work.

From operations to a priority-queue contract

The implementation should specify its exceptional cases as carefully as its successful ones. Reading or deleting a minimum from an empty heap is an underflow error. Inserting into a fixed-capacity array may require a capacity error or an array resize; that storage policy is separate from heap repair. If keys are equal, either item is a valid minimum unless the interface promises a tie-breaking rule. None of these policies changes the structural time bounds, but leaving them implicit can make otherwise correct pseudocode behave unpredictably at the boundary.

The operation costs are worst-case bounds for one update. They arise from the complete tree's h - 1 vertical-edge bound, not from an assumption that real inputs are random. A new smallest key can travel from the last leaf to the root, and a replacement key can travel from the root to the bottom level. Those inputs demonstrate why the logarithmic path bound is sometimes attained.

Worked examples

Worked example

Reading the one-based array

For A = [4, 9, 7, 15, 12, 11, 10], index 3 stores 7. Its parent is at index 1, and its children are at indices 6 and 7, storing 11 and 10. Index 4 has no child because 8>n. The array is a min heap: each listed parent is no larger than its children, although the whole array is not sorted because 9>7.

Worked example

Lecture trace: insert 14

Begin with the lecture heap [13, 21, 16, 24, 31, 19, 68, 65, 26, 32]. Create the new hole at index 11. Its parent at index 5 is 31, so move 31 down. The hole is now index 5; its parent at index 2 is 21, so move 21 down. At index 2, the parent is 13, and 13 ≤ 14, so stop and place 14.

The final array is [13, 14, 16, 24, 21, 19, 68, 65, 26, 32, 31]. Completeness never changed, and only indices 11, 5, and 2 were touched.

Worked example

Lecture trace: delete the minimum

Start from [13, 14, 16, 19, 21, 24, 68, 65, 40, 32, 31]. Save 13, remove the last key 31, and open a hole at the root. Of children 14 and 16, promote 14. Of the next children 19 and 21, promote 19. The next children are 65 and 40; since 31 ≤ 40, place 31 in the hole instead of descending.

The returned minimum is 13, and the remaining heap is [14, 19, 16, 31, 21, 24, 68, 65, 40, 32].

Worked example

Lecture trace: bottom-up build_heap

The lecture begins with the complete-tree array [15, 8, 4, 3, 1, 7, 11, 10, 2, 9, 6, 5, 12, 14, 13]. Leaves 8..15 need no work. After processing indices 7,6,5,4, the array is [15, 8, 4, 2, 1, 5, 11, 10, 3, 9, 6, 7, 12, 14, 13]. After indices 3,2, it is [15, 1, 4, 2, 6, 5, 11, 10, 3, 9, 8, 7, 12, 14, 13]. Sifting index 1 down gives the final heap [1, 2, 4, 3, 6, 5, 11, 10, 15, 9, 8, 7, 12, 14, 13].

The trace also shows why later calls are safe: when the root is processed, its two child subtrees are already heaps.

Operation summary

• find_min: O(1), because the minimum is fixed at index 1.
• insert: O(log n) worst case, because one hole moves up one tree path.
• delete_min: O(log n) worst case, because one hole moves down one tree path.
• bottom-up build_heap: O(n), because most starting nodes have very small downward-edge capacity.
• storage: O(n), because the array keeps one entry per item.

Common mistakes

• Treating the heap array as sorted. Heap order compares ancestors with descendants, not arbitrary neighbours or siblings.
• Using zero-based formulas with a one-based array. Here the formulas are parent floor(i/2), left 2i, and right 2i+1. Zero-based storage uses different formulas.
• Appending without sift-up. Appending preserves the complete shape, but it may violate heap order with the new node's parent.
• Replacing the root without removing the last position. That preserves the number of keys but not the intended complete-tree update. Move the last key and reduce n first.
• Choosing the larger child during sift-down. In a min heap, the smaller child must be promoted so the repaired parent is no larger than either child.
• Charging every sift_down call in build_heap as logarithmic. One call can be logarithmic, but the number of calls decreases geometrically as d increases. Downward-edge-weighted work, not n times the maximum edge count, gives the tight O(n) bound.
• Ignoring empty-heap behaviour. find_min and delete_min require an explicit underflow check; there is no valid root when n=0.

Summary

A binary heap combines a complete binary tree with heap order. Completeness provides logarithmic height and a compact level-order array; min-heap order places a global minimum at the root. Insertion appends and sifts up. Minimum deletion removes the root, moves the last key to a root hole, and sifts down through smaller children. Each repair follows one path, so its worst-case cost is logarithmic. Bottom-up build_heap starts at the last internal node and is linear because the number of nodes decreases geometrically as downward-edge capacity increases. These guarantees make the heap an effective implementation of the minimum-priority-queue abstraction.

Exercises

Checkpoint

In a one-based heap of size 14, what are the parent of index 11 and the valid children of index 7?

Apply the index formulas and check every child index against n.

Checkpoint

Starting from [3, 8, 5, 12, 10, 9], trace insertion of 4. Which direction does the repair move, and what is the final array?

First append at the next legal complete-tree position, then compare with ancestors only.

Checkpoint

Why must delete-min promote the smaller of two children during sift-down?

State the parent-child relation that must hold immediately after the promotion.

Checkpoint

Why is bottom-up build_heap O(n), rather than O(n log n), even though sift_down can take O(log n)?

Group starting nodes by their downward-edge capacity d.

Solutions

Solution · 1. Array relationships

The parent of index 11 is floor(11/2)=5. Index 7 has proposed children 14 and 15; only index 14 is valid because the heap size is 14.

Solution · 2. Insertion trace

Append 4 at index 7. Its parent is index 3, whose key is 5, so move 5 down and move the hole to index 3. The new parent is index 1, whose key is 3; since 3 ≤ 4, stop. The repair is sift-up and the final array is [3, 8, 4, 12, 10, 9, 5].

Solution · 3. Smaller-child choice

Suppose the children have keys a ≤ b. Promoting a makes the new parent no larger than the sibling b, so heap order holds across both outgoing edges. Promoting b would put b above a when a is strictly smaller, immediately violating the min-heap condition.

Solution · 4. Linear construction

If d is the maximum number of downward edges from a node to a leaf, that node can descend at most d edges, while only O(n/2^{d + 1}) nodes have that capacity. Summing the charges gives O(n sum d/2^{d + 1}) = O(n) because the series is constant. The loose O(n log n) multiplication incorrectly charges every internal node the full downward-edge count of the entire tree.