DSA A Heap from Scratch

The problem: a min-heap built by hand

This lesson builds a min-heap from scratch. A min-heap is a structure that always hands back its smallest stored value first. The heap supports three operations: push a value, peek at the smallest value, and pop the smallest value out.

A heap stores its values in one plain list. The list holds a binary tree, which is a tree where each position has at most two children. The parent of index i sits at index (i - 1) // 2, and the children of index i sit at indices 2i + 1 and 2i + 2.

One rule keeps the smallest value on top. Every parent is smaller than or equal to its children. That rule is the heap property, and every operation restores it before finishing.

script = [
    ("push", 9), ("push", 4), ("push", 7),
    ("peek", 4),
    ("pop", 4),
    ("push", 1), ("push", 3),
    ("peek", 1),
    ("pop", 1), ("pop", 3), ("pop", 7), ("pop", 9),
]
for step in script:
    print(step[0], step[1])

Read the script as a contract. Pushes store values. Each peek and pop must produce the value written beside it. The pops near the end leave in rising order, and that order is the whole point of the structure.

Intuition: a plain list already stores everything

The first design keeps values in one unsorted list. A push appends at the end, which is instant. The smallest value hides somewhere in the list, because nothing keeps it near the front.

Peek and pop then pay for that freedom. Both must scan every stored value to find the minimum. The scan is the trap, and it runs again on every single pop.

values = [9, 4, 7, 1, 8, 3]
examined = 0
smallest = None
for v in values:
    examined += 1
    if smallest is None or v < smallest:
        smallest = v
print("smallest:", smallest)
print("values examined:", examined)

Six stored values cost six examinations for one answer. The next pop scans the five that remain. A sorted list would fix the scan, but then each push pays to insert in the right place instead.

Brute force: the naive design, one unsorted list

The naive design is the intuition, written out in full. Push appends. Pop scans the whole list, removes the smallest value it found, and returns it.

The counter below records every value the scans examine. Popping all six values examines six, then five, then four, and so on down to one.

class NaiveBag:
    def __init__(self):
        self.values = []
        self.examined = 0

    def push(self, v):
        self.values.append(v)

    def pop_min(self):
        smallest = None
        for v in self.values:
            self.examined += 1
            if smallest is None or v < smallest:
                smallest = v
        self.values.remove(smallest)
        return smallest

bag = NaiveBag()
for v in (9, 4, 7, 1, 8, 3):
    bag.push(v)
out = []
while bag.values:
    out.append(bag.pop_min())
print("pops:", out)
print("values examined by scans:", bag.examined)

The answers are correct and still expensive. Six values cost 21 examinations, and the count grows with the square of the size. Doubling the stored values roughly quadruples the scanning.

The optimal solution: the real design, sift up and sift down

The real design in one sentence: keep the heap property in a list, restore it after a push by sifting the new value up toward the root, and restore it after a pop by sifting the moved value down toward the leaves. To sift is to swap a value step by step until the property holds around it.

A push appends the value at the end, then sifts it up past any larger parent. A pop takes the root, moves the last value to the root, then sifts it down past its smaller child. Each sift walks one path of the tree, never the whole list.

def sift_up(heap, i):
    while i > 0:
        parent = (i - 1) // 2
        if heap[parent] <= heap[i]:
            break
        heap[parent], heap[i] = heap[i], heap[parent]
        i = parent

def sift_down(heap, i):
    n = len(heap)
    while True:
        left = 2 * i + 1
        right = 2 * i + 2
        smallest = i
        if left < n and heap[left] < heap[smallest]:
            smallest = left
        if right < n and heap[right] < heap[smallest]:
            smallest = right
        if smallest == i:
            break
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

def heap_push(heap, v):
    heap.append(v)
    sift_up(heap, len(heap) - 1)

def heap_pop(heap):
    smallest = heap[0]
    last = heap.pop()
    if heap:
        heap[0] = last
        sift_down(heap, 0)
    return smallest

heap = []
results = []
for v in (9, 4, 7):
    heap_push(heap, v)
results.append(("peek", heap[0]))
results.append(("pop", heap_pop(heap)))
for v in (1, 3):
    heap_push(heap, v)
results.append(("peek", heap[0]))
while heap:
    results.append(("pop", heap_pop(heap)))
for name, value in results:
    print(name, value)

Every peek and pop matches the script from section 1. The same two sift functions also build a heap from a ready list. That build, called heapify, sifts down from the last parent to the root, and the walkthrough uses it next.

Walkthrough: heapify on [9, 4, 7, 1, 8, 3]

Heapify starts at the last parent. In a list of six, the last parent sits at index 2. The build sifts down at index 2, then index 1, then the root at index 0.

Leaves need no work. A leaf has no children, so the heap property already holds below it. Starting at the last parent skips half the list at once.

def sift_down(heap, i, counter):
    n = len(heap)
    while True:
        left = 2 * i + 1
        right = 2 * i + 2
        smallest = i
        if left < n and heap[left] < heap[smallest]:
            smallest = left
        if right < n and heap[right] < heap[smallest]:
            smallest = right
        if smallest == i:
            break
        heap[i], heap[smallest] = heap[smallest], heap[i]
        counter[0] += 1
        i = smallest

heap = [9, 4, 7, 1, 8, 3]
counter = [0]
for i in range(len(heap) // 2 - 1, -1, -1):
    sift_down(heap, i, counter)
    print("after sifting index", i, ":", heap, "- swaps so far:", counter[0])
print("root:", heap[0])

The root ends at 1, the smallest value. Four swaps built the whole heap. The swap count below the list length is the visible sign that most values sifted only a short distance.

Complexity

A heap push or pop sifts along one root-to-leaf path, and a tree of n values has about log2 n levels, so each operation costs O(log n) swaps. The naive design pays a full scan per pop, so its pop costs O(n).

Heapify costs O(n) in total, because most values sit near the leaves and sift only one or two steps. Both designs store their values in one list, so both use O(n) space.

for n in (6, 12, 24):
    naive_scans = n * (n + 1) // 2
    levels = n.bit_length()
    print("values", n, "- naive pop-all scans:", naive_scans, " heap path length at most:", levels)

Counts beat clocks here. At 24 values the naive design scans 300 values to empty itself. A heap operation never walks more than 5 levels, however the values arrived.

Edge cases and pitfalls

Sift down must swap with the smaller child. Swapping with the larger child can leave the smaller child below a bigger parent, and the heap property breaks. The run below shows that exact failure.

An empty heap has no smallest value. Peek and pop guard for it and answer None. A one-value heap pops its only value and needs no sift at all.

def sift_down(heap, i):
    n = len(heap)
    while True:
        left = 2 * i + 1
        right = 2 * i + 2
        smallest = i
        if left < n and heap[left] < heap[smallest]:
            smallest = left
        if right < n and heap[right] < heap[smallest]:
            smallest = right
        if smallest == i:
            break
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

def heap_pop(heap):
    if not heap:
        return None
    smallest = heap[0]
    last = heap.pop()
    if heap:
        heap[0] = last
        sift_down(heap, 0)
    return smallest

print("pop from empty:", heap_pop([]))
heap = [5]
print("pop the only value:", heap_pop(heap), "- heap now:", heap)
heap = [2, 2, 2]
print("duplicates pop:", heap_pop(heap), heap_pop(heap), heap_pop(heap))
broken = [9, 2, 3, 4]
broken[0], broken[2] = broken[2], broken[0]
print("after swapping with the larger child:", broken)
print("parent 3 above child 2 breaks the property:", broken[0] > broken[1])

The broken list puts 3 above its child 2. One wrong child choice undoes the sift. Picking the smaller child every time is what keeps the root trustworthy.