7.1 Heaps

Prerequisite: Red-Black Tree | Next Section: Priority Queue. This page starts from the array representation of a complete binary tree and proceeds to implement heapify-up, heapify-down, Floyd's heap construction, and heap sort.

1. How a complete binary tree fits into an array

In a complete binary tree, the last level is filled from left to right, so after level numbering, the nodes can be stored consecutively in an array.

Index:  0  1  2  3  4  5  6
Array: [1, 3, 2, 7, 6, 4, 5]

             1
          /     \
         3       2
       /  \    / \
      7    6   4   5

Zero-based indexing i:

• For i > 0, the parent is (i - 1) // 2; the root has no parent;
• Left child is 2 * i + 1;
• The right child is 2 * i + 2.

A min-heap requires each parent to satisfy <= with both children, while a max-heap operates in the opposite direction. Note the boundaries: the invariant does not compare siblings nor different subtrees. The root can be guaranteed to hold the minimum value; the second smallest value may only be among the root's children, and it is not guaranteed that array index 1 contains the second smallest value. Finding any arbitrary value remains worst-case O(n).

2. A Checkable Minimum Heap

Place a new element at the end of the array and compare it with its parent. Swap upward while it is smaller: this is sift-up. After removing the root, move the last element into its place, compare it with the smaller child, and swap downward as needed: this is sift-down.

The generic implementation below uses only <, as Python heapq does. Elements must have a consistent ordering, excluding values such as NaN, and their comparison fields must remain unchanged while in the heap. Type annotations do not enforce this contract, and this implementation does not roll back when a comparison raises an exception.

from __future__ import annotations

from collections.abc import Iterable
from typing import Generic, TypeVar

T = TypeVar("T")

class MinHeap(Generic[T]):
    def __init__(self, values: Iterable[T] = ()) -> None:
        self._data = list(values)
        for i in range(len(self._data) // 2 - 1, -1, -1):
            self._sift_down(i)

    @classmethod
    def heapify(cls, values: Iterable[T]) -> "MinHeap[T]":
        return cls(values)

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

    def push(self, value: T) -> None:
        self._data.append(value)
        i = len(self._data) - 1
        while i > 0:
            parent = (i - 1) // 2
            if not self._data[i] < self._data[parent]:
                break
            self._data[parent], self._data[i] = self._data[i], self._data[parent]
            i = parent

    def peek(self) -> T:
        if not self._data:
            raise IndexError("peek from empty heap")
        return self._data[0]

    def pop(self) -> T:
        if not self._data:
            raise IndexError("pop from empty heap")
        root = self._data[0]
        last = self._data.pop()
        if self._data:
            self._data[0] = last
            self._sift_down(0)
        return root

    def _sift_down(self, i: int) -> None:
        n = len(self._data)
        while True:
            smallest = i
            left = 2 * i + 1
            right = 2 * i + 2
            if left < n and self._data[left] < self._data[smallest]:
                smallest = left
            if right < n and self._data[right] < self._data[smallest]:
                smallest = right
            if smallest == i:
                return
            self._data[i], self._data[smallest] = self._data[smallest], self._data[i]
            i = smallest

    def to_list(self) -> list[T]:
        return list(self._data)

    def is_valid(self) -> bool:
        n = len(self._data)
        for i in range(n // 2):
            left = 2 * i + 1
            right = 2 * i + 2
            if left < n and self._data[left] < self._data[i]:
                return False
            if right < n and self._data[right] < self._data[i]:
                return False
        return True

if __name__ == "__main__":
    heap = MinHeap([5, 3, 8, 1, 7])
    heap.push(0)
    assert heap.is_valid()
    print([heap.pop() for _ in range(len(heap))])

The output is [0, 1, 3, 5, 7, 8]. The intermediate state of the array may differ from others' implementations, as long as the elements are the same and the parent invariants remain valid, all such heaps are legitimate.

Trace One Sift-Up

Insert 0 at [1, 3, 2, 7, 6, 4, 5]:

1. 0 reaches index 7, parent node index is 3, value is 7;
2. After swapping, at index 3, the parent node index is 1, and the value is 3;
3. After the swap, it reaches index 1, and the parent node is the root 1;
4. Finally swap to get [0, 1, 2, 3, 6, 4, 5, 7].

Sift-up traverses at most the tree height, so heap adjustment costs O(log n). This implementation uses a Python list: an individual append can copy O(n) references during resizing. Amortizing those resizes gives O(log(n+1)) insertion time.

Trace One Sift-Down

Remove the root from [0, 1, 2, 3, 6, 4, 5, 7]:

1. Save 0, and drop the trailing 7 to the root;
2. The children of the root are 1 and 2; select the smaller 1 and swap it;
3. 7's new children are 3 and 6; choose 3 to swap;
4. 7 reaches the leaf, yielding [1, 3, 2, 7, 6, 4, 5].

peek reads the root in O(1). Sift-down visits at most the tree height, so adjustment costs O(log n). A CPython list's tail pop may also shrink its storage; the complete operation is amortized O(log(n+1)), while an individual resize may cost more. Checking an empty heap takes constant time.

3. Why Floyd's Heap Construction Is O(n)

Given an unordered array, there's no need to push one by one. Floyd starts from the last internal node n // 2 - 1 and processes each node in reverse, filtering down. When processing a node, its two subtrees are already heaps.

Leaves occupy about half, with 0 layers of movement; nodes with height at least 1 are no more than n/2, and nodes with height at least 2 are no more than n/4. Billing is based on "how many layers each node might descend":

total levels descended <= floor(n/2) + floor(n/4) + ... + floor(n/2^floor(log2(n))) < n
(n >= 1)

This finite sum stops at the tree height and counts levels descended. Comparisons at each level and fixed work at each internal node still contribute. Princeton's analysis bounds both exchanges and comparisons linearly. Including the Θ(n) input copy, this constructor takes Θ(n) time. Repeated insertion has an O(n log n) upper bound.

The constructor stores a Θ(n) shallow copy, and to_list() returns another shallow copy. Replacing slots in the original list does not change the heap, but mutable element objects remain shared. Changing an object's comparison fields can break the invariant. is_valid() scans parent-child relationships in O(n) time and O(1) auxiliary space.

4. Heap Sort

In-place heap sort in ascending order builds a max heap. In each round, the maximum value is swapped from the root to the end of the current interval, then the interval is shortened and the root is sifted down.

from typing import TypeVar

T = TypeVar("T")

def heap_sort(values: list[T]) -> list[T]:
    def sift_down(root: int, end: int) -> None:
        while True:
            largest = root
            left = 2 * root + 1
            right = 2 * root + 2
            if left < end and values[largest] < values[left]:
                largest = left
            if right < end and values[largest] < values[right]:
                largest = right
            if largest == root:
                return
            values[root], values[largest] = values[largest], values[root]
            root = largest

    n = len(values)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(i, n)
    for end in range(n - 1, 0, -1):
        values[0], values[end] = values[end], values[0]
        sift_down(0, end)
    return values

if __name__ == "__main__":
    data = [4, 10, 3, 5, 1]
    print(heap_sort(data))

Building the heap is O(n), followed by n - 1 heapify operations, each taking at most O(log n) time, so the total time is O(n log n). The function modifies the input list and returns that same list; the example prints [1, 3, 4, 5, 10]. It uses only a constant number of extra variables, so auxiliary space is O(1). Far-distance swaps may alter the relative order of equal elements, so heap sort is unstable.

5. Debugging Checklist

Symptoms	Check First
The pop root is not the smallest	Does downward filtering choose the smaller one among left and right children
Out-of-bounds access on even-length arrays	Does it check right < n before reading the right child
Missing root in heap build	Does reverse interval include 0
Caller modifies input, heap also changes	Does input get copied at construction, rather than storing a reference
Printing an array seems unordered	This is usually normal; use is_valid to check parent-child relationships
Ambiguous result from an empty heap	Are peek and pop consistently throwing IndexError

6. When a Heap Is the Wrong Fit

To query predecessors, successors, or any range, return to a balanced BST. To frequently locate and modify arbitrary nodes by identifier, a regular binary heap lacks an index table, and lookup remains O(n). To produce a fully ordered output, final output still requires repeated pop or sorting.

A d-ary heap changes the number of children per node from 2 to d. The tree becomes shallower, but each sift-down level must compare more children. Actual performance depends on data size, comparison cost, and memory layout; tree height alone does not prove that a four-ary heap will be faster.

From Heap Structure to Queue Interface

Sift-up moves new elements along the parent chain; sift-down moves the replacement root toward its smaller child. Floyd's construction also uses sift-down. Its linear cost comes from processing order: leaves need no movement, and fewer nodes are close enough to the root to move far. The array doesn't need to be globally sorted at intermediate stages; only the parent-child invariant and the root extremum matter.

The next section encapsulates this structure into a priority queue to continue handling tasks of the same priority, task cancellation, and candidate sets.