Heaps & Priority Queues

A heap is a clever way to always grab the smallest (or largest) item fast. It looks like a tree, but it lives inside a plain array. A priority queue is just a heap with a friendly name: push items in any order, and pop always returns the most important one first. Here we build a min-heap, where the smallest value sits at the top.

The idea

A min-heap follows one rule: every parent is smaller than its children. That is all. Because of that rule, the smallest value can only be in one place — the very top (the root).

The trick is that we never need real tree pointers. We store the heap as a flat array and use simple math to move between a node and its family:

To insert a value we do two things. First, drop it at the end of the array — that always keeps the tree a nice complete shape. Second, sift it up: compare it with its parent and swap if it is smaller, again and again, until it is no longer smaller than its parent (or it reaches the root).

Walk through it

Press Play on the right, or step with Next / Back. We start with a valid min-heap and insert the value 2.

• The new value lands at the end (index 5). Its parent is (5 - 1) // 2 = 2, which holds 5.
• 2 < 5, so they swap. Now 2 is at index 2. Its parent is (2 - 1) // 2 = 0, the root, which holds 3.
• 2 < 3, so they swap again. Now 2 is at the root.
• Index 0 has no parent, so we stop. The heap rule holds again, and 2 is the new smallest value.

Notice that the tree node and the array cell move together — they are the same item shown two ways. The pair being compared turns blue; a swap turns them red and slides both views.

The code, line by line

def heap_push(heap, value):
    heap.append(value)        # add at the end
    i = len(heap) - 1
    while i > 0:              # until we reach the root
        parent = (i - 1) // 2
        if heap[i] < heap[parent]:
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent        # follow the value up
        else:
            break

• Line 2 appends the value to the end of the array — O(1).
• Line 3 sets i to that last index, where the value now sits.
• Line 4 is the sift-up loop: keep going until we hit the root (i == 0).
• Line 5 finds the parent index with (i - 1) // 2. The // is integer division, so it rounds down.
• Line 6 checks the heap rule. If the child is smaller than its parent, they are out of order.
• Line 7 swaps them, and line 8 moves i up to follow the value to its new spot.
• Line 10 breaks the moment the value is in place — no need to keep climbing.

Python's standard library has this built in as heapq.heappush(heap, value), which does exactly this.

Complexity

Why O(log n)? A heap is a complete binary tree, so it has about log₂ n levels. Sift-up moves the new value up one level per swap, so it can do at most log n swaps. The space is O(n) simply to store the n values in the array — no extra pointers needed.

When to use / pitfalls

Practice