Heaps and priority queues

Use a min-heap when you repeatedly need the earliest deadline. It keeps the next item easy to reach without sorting every item.

Read the two invariants

         2                  array: [2, 5, 3, 9, 7]
       /   \                index:  0  1  2  3  4
      5     3
     / \
    9   7

A binary heap has a complete shape: fill each level left to right. In a min-heap, every parent is no greater than its children. Together, these rules put a minimum at the root and bound the height by O(log n).

The array stores the tree level by level. For index i, children are 2i + 1 and 2i + 2. The parent is (i − 1) divided by 2, rounded down.

The array is not sorted: 5 comes before 3. Siblings need no particular order. A max-heap reverses the comparison and puts a maximum at the root.

Trace insertion and removal

Insert 1 into the diagram. Append it at index 5, under 3. Swap 1 with 3, then with 2. The array becomes [1, 5, 2, 9, 7, 3]. This is called sifting up.

Remove the minimum. Save 1, move the final 3 to the root, and shorten the array. Compare 3 with its children 5 and 2. Swap with the smaller child, 2. The array becomes [2, 5, 3, 9, 7]. This is sifting down.

Choosing the smaller child matters: swapping with 5 would leave 5 above 2 and break the invariant.

Know what a heap cannot answer cheaply

Array growth can add an occasional O(n) allocation to insertion; the O(log n) insertion bound is amortized when using a dynamic array.

Bottom-up construction sifts down from the last parent toward the root. Most nodes are near the leaves and move only a short distance. Summing those distances gives O(n), unlike n separate insertions' O(n log n) upper bound.

For ordered traversal and predecessor queries, use a balanced search tree. For one fixed batch, sorting may be simpler. For changing priorities, an indexed heap can map each item to its array position. Every swap must update that map. Another approach inserts new versions and skips stale entries later, at the cost of extra space.

Predict and modify

1. Is [1, 4, 2, 8, 5, 3] a valid min-heap?
2. Can a minimum occur anywhere except the root?
3. Add deterministic ordering for jobs with equal deadlines.

def push(heap, value):
    heap.append(value)
    child = len(heap) - 1
    while child > 0:
        parent = (child - 1) // 2
        if heap[parent] <= heap[child]:
            break
        heap[parent], heap[child] = heap[child], heap[parent]
        child = parent


def pop_min(heap):
    if not heap:
        raise IndexError("heap is empty")
    minimum = heap[0]
    last = heap.pop()
    if not heap:
        return minimum
    heap[0] = last
    parent = 0
    while 2 * parent + 1 < len(heap):
        child = 2 * parent + 1
        if child + 1 < len(heap) and heap[child + 1] < heap[child]:
            child += 1
        if heap[parent] <= heap[child]:
            break
        heap[parent], heap[child] = heap[child], heap[parent]
        parent = child
    return minimum


heap = []
for value in [2, 5, 3, 9, 7, 1, 1]:
    push(heap, value)
    assert all(heap[(i - 1) // 2] <= heap[i] for i in range(1, len(heap)))
assert [pop_min(heap) for _ in range(7)] == [1, 1, 2, 3, 5, 7, 9]
assert heap == []

Apply repeated removal in Merge k Sorted Lists.

Next: Graphs and their representations.