Heapify: Sift-Up & Sift-Down

The problem the operations solve

The previous lesson gave us the heap property (parent ≤ both children, for a min-heap) and showed the tree lives in a flat array. But a static heap is useless — we need to insert new elements and remove the minimum, and every such change threatens to violate the invariant. The two repair operations that fix a single local violation are sift-up and sift-down, and every heap operation is built from them. Both cost O(log n) for the same structural reason, which we'll pin down precisely, and then we'll meet the module's one genuinely surprising result: building a heap from an unsorted array is O(n), not O(n log n).

Throughout, remember the array indexing from last lesson: for node i, left = 2i+1, right = 2i+2, parent = (i−1)//2.

Sift-up: repair an element that's too small for where it sits

Picture a vertical stack of boxes on a shelf bracket system, stacked by weight, lightest boxes allowed only above heavier ones directly underneath — but nobody checks two boxes on the same shelf against each other, only a box against what's directly below it. Now a new, very light box gets set down at the very bottom of the stack, resting under a much heavier box. That's unstable — a light box shouldn't be under a heavy one — so it pushes upward, swapping places with the heavier box above it, and keeps rising one slot at a time until it finally rests under a box no heavier than itself, or reaches the very top.

Insertion works like this: append the new value to the end of the array. That keeps the tree complete (the new node fills the next left-to-right slot), but the value may be smaller than its parent, violating the invariant at that one spot. Everywhere else the heap is still fine. So we only need to fix this one node, by sifting it up: compare it to its parent; if it's smaller, swap; repeat from the new position until it's ≥ its parent or reaches the root.

After appending 1, the value sifts up until the heap property holds again:

Trace: append into [2, 4, 3, 7, 5] → [2, 4, 3, 7, 5, 1], then swap with parent 4, then with root 2, landing at [1, 2, 3, 7, 5, 4].

Why is this correct? When we swap the new value v up past its parent p, we push p down into the slot v vacated. We must check that p still dominates that slot's subtree — and it does: p was already ≤ its other child (the heap was valid there before), and p ≤ v's former subtree because v was the smallest thing in it (it just arrived as a leaf). So each swap fixes the violation locally without creating a new one below. The value climbs until it finds a parent no larger than itself.

Sift-down: repair an element that's too large for where it sits

Same shelf bracket, mirrored. Suppose you remove the lightest box from the very top of the stack, and to fill the gap you grab whatever box happens to be sitting at the very bottom and drop it on top instead. It's almost certainly too heavy to belong there — so it sinks, swapping places with whichever of the two boxes directly beneath it is lighter (never the heavier one — putting a heavy box under an already- heavy one would just move the problem sideways instead of solving it), and keeps sinking one slot at a time until it settles under boxes no lighter than itself, or hits the bottom shelf.

Extract-min is the mirror image. The minimum is at the root, index 0. We want to remove it while keeping the tree complete. The trick: swap the root with the last element, then shrink the array by one (removing what is now the old minimum from the end — cheap, no shifting). The last element is now sitting at the root, almost certainly too large. Every other node still satisfies the invariant. So we fix the root by sifting it down: compare it to its two children, swap with the smaller child if that child is smaller than it, and repeat until both children are ≥ it (or it becomes a leaf).

Why swap with the smaller child specifically? The child that moves up becomes the new parent of the other child, so it must be ≤ both. Only the smaller of the two children is guaranteed ≤ the other — pick the larger and you'd immediately re-violate the invariant on the other side.

Why both are O(log n)

Both operations walk a single root-to-leaf path, doing O(1) work per step (a constant number of comparisons and one swap). The number of steps is bounded by the tree's height. A complete binary tree with n nodes has height ⌊log₂ n⌋: each level k holds up to 2^k nodes, so to hold n nodes you need about log₂ n levels (from last lesson's counting: 2^0 + ... + 2^h = 2^(h+1) − 1 ≥ n forces h ≥ log₂(n+1) − 1). Sift-up traverses at most one node per level from a leaf to the root; sift-down at most one per level from the root to a leaf. Either way, at most ⌊log₂ n⌋ steps, each O(1) → O(log n). No input makes the path longer, because completeness caps the height — that's the guarantee the balanced shape buys us.

From scratch: a full MinHeap and MaxHeap

Python ships heapq (we cover it below), but implementing the structure once, by hand, is the point of this lesson — you should be able to write these two operations from memory. Here is a complete min-heap. In TypeScript there is no built-in heap at all, so this class is what every problem lesson in this module will reuse.

class MinHeap:
    def __init__(self) -> None:
        self._data: list[int] = []

    def __len__(self) -> int:
        return len(self._data)

    def peek(self) -> int:
        return self._data[0]            # global min, O(1)

    def push(self, value: int) -> None:
        self._data.append(value)        # keep the tree complete
        self._sift_up(len(self._data) - 1)

    def pop(self) -> int:
        d = self._data
        d[0], d[-1] = d[-1], d[0]        # move min to the end
        minimum = d.pop()               # remove it, O(1)
        if d:
            self._sift_down(0)
        return minimum

    def _sift_up(self, i: int) -> None:
        d = self._data
        while i > 0:
            p = (i - 1) // 2
            if d[i] < d[p]:             # smaller than parent: climb
                d[i], d[p] = d[p], d[i]
                i = p
            else:
                break                   # invariant satisfied
    def _sift_down(self, i: int) -> None:
        d = self._data
        n = len(d)
        while True:
            smallest = i
            l, r = 2 * i + 1, 2 * i + 2
            if l < n and d[l] < d[smallest]:
                smallest = l
            if r < n and d[r] < d[smallest]:
                smallest = r
            if smallest == i:           # both children ≥ i: stop
                break
            d[i], d[smallest] = d[smallest], d[i]
            i = smallest

A max-heap is the identical structure with every comparison reversed (> instead of <, largest instead of smallest). Rather than duplicate the code, many implementations take a comparator; for this module, mentally swap the comparisons — we'll show the max-heap variant where a problem needs it (e.g. K Closest Points).

Python's heapq: a min-heap, and the max-heap workaround

Python's heapq is exactly the array-backed binary heap above, exposed as free functions operating on a plain list:

import heapq

h: list[int] = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
print(h[0])            # 1 — the min is always at index 0
print(heapq.heappop(h))  # 1, then re-heapifies

# heapq is MIN-ONLY. To get a max-heap, negate on the way in and out:
maxh: list[int] = []
for v in (5, 1, 3):
    heapq.heappush(maxh, -v)     # store negatives
largest = -maxh[0]               # 5 — negate back when reading
largest = -heapq.heappop(maxh)   # 5 — and when popping

The negation trick trips people up, so be explicit about why it works: a min-heap always hands you the algebraically smallest stored value. If you store −v for every v, then the smallest stored value is −(max v), so negating the heap's output recovers the true maximum. Every comparison −a < −b is exactly a > b, so ordering by negatives is reverse ordering. The catch to remember: negate both on push and on peek/pop, and it only works cleanly for numbers (for tuples or objects you'd negate the key or use a comparator/wrapper).

Build-heap: O(n), not O(n log n)

Now the surprising result. Suppose you have an unsorted array of n elements and want to turn it into a heap. The obvious way: start with an empty heap and push all n elements. Each push is O(log n), so this is O(n log n). Correct, but not optimal.

There is a better way — heapify — that runs in O(n). Take the raw array as-is (it's already a complete tree, just not a valid heap), and sift down every non-leaf node, working from the last non-leaf backward to the root:

def build_heap(arr: list[int]) -> None:
    n = len(arr)
    # last non-leaf is the parent of the last element:
    start = (n - 2) // 2
    for i in range(start, -1, -1):      # from last non-leaf up to root
        _sift_down_on(arr, i, n)

(Python's heapq.heapify(arr) does exactly this in one C call.) Why go backward from the bottom? Sift-down assumes both of a node's subtrees are already valid heaps and only its own value might be misplaced. Processing bottom-up guarantees that precondition: when we reach node i, every node below it has already been sifted, so its children are valid heap roots. Leaves need no work (no children to violate against), which is why we start at the last non-leaf.

That starting index, (n−2)//2, isn't a number to memorize — it falls straight out of last lesson's parent(i) = (i−1)//2 formula. The last element in the array sits at index n−1, so its parent — the last node that could possibly have any children — is at parent(n−1) = ((n−1)−1)//2 = (n−2)//2. Every index after that is necessarily a leaf (it comes after the last node with children), so sifting starts exactly there.

The complexity claim. The naive "n pushes × O(log n)" bound is O(n log n), and it is a genuine over-estimate here. It assumes every element travels the full height of the tree. But heapify sifts down, and the overwhelming majority of nodes are near the bottom, where sift-down can only travel a tiny distance. Let's sum the actual work.

Group the nodes by their height (distance to the farthest leaf below them, so leaves have height 0). In a complete tree of n nodes:

• height 0 (leaves): about n/2 nodes
• height 1: about n/4 nodes
• height 2: about n/8 nodes
• ... in general, at most ⌈n / 2^(h+1)⌉ nodes of height h

Where that bound comes from: a node of height h or more must be the root of a subtree with at least h+1 levels, which (last lesson's counting) holds at least 2^(h+1) − 1 nodes — so at most n / 2^(h+1) of the tree's n nodes can afford to sit that deep from their own farthest leaf. Height 0 (every leaf) is the extreme case of this: a subtree of height ≥ 0 needs only 1 node, so up to n/2^1 = n/2 nodes qualify — matching the bullet above.

A node of height h sifts down at most h steps. So total work is bounded by summing (number of nodes at height h) × (steps h) over all heights up to log n:

Total  ≤  Σ (h = 0 .. log n)  (n / 2^(h+1)) · h
       =  (n/2) · Σ (h = 0 .. ∞)  h / 2^h

The remaining sum Σ h/2^h is a standard convergent series. Its exact value is 2 (it's x/(1−x)² at x = 1/2, giving (1/2)/(1/4) = 2). So:

The intuition behind the algebra: the expensive nodes (the ones that can sift far, near the top) are few — only the root can travel the full log n, its two children only log n − 1, and so on. The many cheap nodes near the bottom dominate the count but each does almost no work. The work per level halves as you go up while the distance only increases by one, so the total is a converging geometric-ish sum, not a growing one. That's the whole reason it telescopes to O(n) instead of O(n log n).

Trace it on arr = [5, 3, 8, 4, 1, 9, 2] (n = 7, so start = (7−2)//2 = 2). sift_down(2): node 8 (index 2) has children 9 (index 5) and 2 (index 6); 2 is smaller, and 2 < 8, so swap — array becomes [5, 3, 2, 4, 1, 9, 8], and index 6 is a leaf, so this sift is done after one swap. sift_down(1): node 3 (index 1) has children 4 (index 3) and 1 (index 4); 1 is smaller and 1 < 3, so swap — [5, 1, 2, 4, 3, 9, 8]; index 4 is also a leaf, done. sift_down(0): node 5 has children 1 (index 1) and 2 (index 2); 1 is smaller and 1 < 5, so swap — [1, 5, 2, 4, 3, 9, 8] — but 5 (now at index 1) still has children 4 (index 3) and 3 (index 4); 3 is smaller and 3 < 5, so it keeps sinking — one more swap gives [1, 3, 2, 4, 5, 9, 8]. Every node's value is now ≤ both its children — a valid heap, built in four total swaps over seven elements, no O(n log n) pass required.

Same array, same heap, different construction cost — one of the few places where the "obvious" bound is loose and the real answer is better.