Heaps and Priority Queues

The problem heaps solve

Sometimes a program needs to repeatedly answer one question: “of everything I am holding right now, what is the smallest (or largest) item?” Then it takes that item out, and new items keep arriving. An emergency room treats the most urgent patient next. A task scheduler runs the highest-priority job first. A route finder always expands the cheapest path so far.

You could keep all the items in a plain list and, each time you need the smallest, scan the whole list. Scanning takes time proportional to the number of items: with n items that is O(n) work per question, and if you ask the question many times it adds up. Big-O notation describes how the work grows as the input grows; O(n) means the work grows in direct proportion to n, and O(log n) means it grows very slowly (doubling the items adds only one more unit of work).

A heap is a data structure built for exactly this pattern. It keeps the smallest item instantly available, and both inserting a new item and removing the smallest cost only O(log n). The result is fast access to the extreme item without keeping everything fully sorted.

What a heap is

A heap is a kind of binary tree. A tree is a structure of connected nodes; each node holds a value. In a binary tree every node has at most two children, called the left child and the right child. The single node at the top, with no parent, is the root.

A heap adds two rules.

The first rule is the heap property. In a min-heap, every node’s value is less than or equal to the values of its children. Written as a rule: parent <= each child. This does not mean the tree is sorted; it guarantees only that no node is smaller than its parent, and that holds at every node. Because every parent is no larger than its children all the way up the tree, the smallest value in the entire heap sits at the root. A max-heap flips the comparison (parent >= each child) so the largest value sits at the root.

The second rule is shape: a heap is a complete binary tree. That means every level of the tree is completely filled except possibly the last, and the last level is filled from the left with no gaps. This tidy shape is what keeps the height of the tree at about log n, and the height is what makes the operations O(log n).

Here is a small min-heap holding the values 1, 3, 5, 4, 8, 9, 7:

graph TD
    A[1] --> B[3]
    A --> C[5]
    B --> D[4]
    B --> E[8]
    C --> F[9]
    C --> G[7]

Check the heap property on any node: 1 is below 3 and 5; 3 is below 4 and 8; 5 is below 9 and 7. Every parent is smaller than its children, so the root 1 is the overall minimum. Notice the tree is not sorted left to right; 5 sits to the right of 3 even though the level below 3 contains an 8. The heap promises only the parent-child relationship, nothing more.

Storing a tree in a flat array

A complete binary tree needs no actual node objects and no pointers between them. Because the shape is so regular, the whole tree fits in an ordinary list (an array, a numbered sequence of slots), and simple arithmetic on the slot numbers takes you between parents and children.

Number the nodes level by level, left to right, starting at 0. The heap above becomes:

index:  0  1  2  3  4  5  6
value:  1  3  5  4  8  9  7

For the node stored at index i, the positions of its relatives are:

• left child: 2*i + 1
• right child: 2*i + 2
• parent: (i - 1) // 2 (// is integer division, which discards the remainder)

Check it. The root is at index 0; its children are at 2*0+1 = 1 and 2*0+2 = 2, holding 3 and 5. The node at index 1 (value 3) has children at indices 3 and 4, holding 4 and 8. The node at index 4 (value 8) has parent at (4-1)//2 = 1, which is the 3. The arithmetic and the picture agree.

values = [1, 3, 5, 4, 8, 9, 7]
i = 1                       # the node holding value 3
print(values[2*i + 1])      # -> 4   (left child)
print(values[2*i + 2])      # -> 8   (right child)
print(values[(i - 1) // 2]) # -> 1   (parent, the root)

This is why heaps are efficient in practice as well as in theory: an array is contiguous in memory and has no per-node overhead, so these lookups are just index math.

Push: adding an item with sift-up

To add a value while keeping both rules true, you do the following. Put the new value in the next free slot at the end of the array. That keeps the complete-tree shape intact, but the new value might be smaller than its parent, which would break the heap property. So you repair it by sift-up: compare the new value with its parent, and if the value is smaller, swap them. Repeat with the new position, walking up toward the root, stopping as soon as the parent is smaller-or-equal or you reach the root.

The value climbs at most the height of the tree, which is about log n steps, so a push is O(log n) time.

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

def push(heap, value):
    heap.append(value)          # place at the end
    sift_up(heap, len(heap) - 1)

h = [1, 3, 5, 4, 8, 9, 7]
push(h, 2)
print(h)   # -> [1, 2, 5, 3, 8, 9, 7, 4]

The 2 was appended at index 7, compared with its parent 4 at index 3 (2 < 4, swap up to index 3), then its new parent 3 at index 1 (2 < 3, swap up to index 1), then its parent 1 at index 0 (2 is not < 1, stop). The root is still the minimum.

Before 2 enters, the heap is the one we started with:

graph TD
    A[1] --> B[3]
    A --> C[5]
    B --> D[4]
    B --> E[8]
    C --> F[9]
    C --> G[7]

After the push and sift-up, 2 has climbed until 3 and 1 sit above it, and the 4 it displaced settled into 2’s old slot at the bottom:

graph TD
    A[1] --> B[2]
    A --> C[5]
    B --> D[3]
    B --> E[8]
    C --> F[9]
    C --> G[7]
    D --> H[4]

The full array state after every swap of the sift-up, starting from the moment 2 is appended:

Each row is the entire heap immediately after that step, so you can watch the 2 travel from index 7 up to index 1 one swap at a time.

Pop: removing the smallest with sift-down

To remove the smallest item, you take the root (index 0), since that is the minimum. But you cannot just delete the front of an array cheaply, and you must preserve the shape. The trick: move the last element into the root position and shrink the array by one. The shape stays complete, but that value at the top is probably too big, breaking the heap property. Repair it with sift-down: compare the node with its two children, swap it with the smaller child if that child is smaller than the node, and keep walking down until both children are larger-or-equal or you reach the bottom.

Swapping with the smaller child is what keeps the property intact: the new parent must be no larger than either child. This also runs in at most log n steps, so a pop is O(log n) time.

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:       # already in the right place
            break
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

def pop(heap):
    smallest = heap[0]
    last = heap.pop()           # remove the final element
    if heap:                    # if anything is left, put it on top and repair
        heap[0] = last
        sift_down(heap, 0)
    return smallest

h = [1, 2, 5, 3, 8, 9, 7, 4]
print(pop(h))   # -> 1
print(h)        # -> [2, 3, 5, 4, 8, 9, 7]

The left < n and right < n checks matter: a node near the bottom may have one child or none, and reading past the end of the array would be a bug. Guarding the child indices against the current length n handles that.

The heap before the pop is [1, 2, 5, 3, 8, 9, 7, 4]:

graph TD
    A[1] --> B[2]
    A --> C[5]
    B --> D[3]
    B --> E[8]
    C --> F[9]
    C --> G[7]
    D --> H[4]

To pop, we take the root 1, move the last element 4 into the root slot, drop the array by one, then sift that 4 down along the path of smaller children. It ends up here ([2, 3, 5, 4, 8, 9, 7]), with 2 promoted to the root:

graph TD
    A[2] --> B[3]
    A --> C[5]
    B --> D[4]
    B --> E[8]
    C --> F[9]
    C --> G[7]

The array state after each step of the pop, starting the moment the last element 4 has been moved to the root:

The 4 sinks from index 0 to index 3, one level per swap, always trading places with the smaller of its two children so the heap property is restored at each node it passes.

heapify: building a heap from an existing list in O(n)

Suppose you already have a list of n values in random order and want to turn the whole thing into a heap. You could push them one at a time, which is n pushes at O(log n) each, giving O(n log n). There is a faster way called heapify: run sift-down on every node that has a child, working from the last such node up to the root.

Half the nodes are leaves (they have no children, so nothing to do), and nodes closer to the bottom can only sift down a short distance. When you add up the work carefully, the total is O(n) time, better than O(n log n). The space is O(1) extra, because it rearranges the list in place.

def heapify(values):
    n = len(values)
    start = (n // 2) - 1        # last node that has at least one child
    for i in range(start, -1, -1):
        sift_down(values, i)

data = [9, 4, 7, 1, 8, 3, 5]
heapify(data)
print(data)      # -> [1, 4, 3, 9, 8, 7, 5]
print(data[0])   # -> 1   (the minimum is now at the root)

The exact array can differ depending on swap order; what is guaranteed is that the heap property holds and data[0] is the minimum.

The starting list [9, 4, 7, 1, 8, 3, 5] viewed as a complete tree, before any sift-down runs. Note the root 9 is larger than its children, so the heap property is badly broken:

graph TD
    A[9] --> B[4]
    A --> C[7]
    B --> D[1]
    B --> E[8]
    C --> F[3]
    C --> G[5]

After heapify runs sift-down on index 2, then 1, then 0, the same slots hold a valid heap ([1, 4, 3, 9, 8, 7, 5]), with the minimum 1 pulled up to the root:

graph TD
    A[1] --> B[4]
    A --> C[3]
    B --> D[9]
    B --> E[8]
    C --> F[7]
    C --> G[5]

Python’s built-in: the heapq module

You will rarely write these functions by hand in real code. Python ships a module called heapq that implements a min-heap directly on a plain list. Learning the mechanics above is what lets you use heapq correctly and reason about its cost. The important functions:

• heapq.heappush(heap, item) — add an item, O(log n).
• heapq.heappop(heap) — remove and return the smallest item, O(log n).
• heapq.heapify(list) — turn an existing list into a heap in place, O(n).
• heap[0] — peek at the smallest item without removing it, O(1).

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 8)
heapq.heappush(heap, 3)

print(heap[0])            # -> 1   (peek at the minimum, no removal)
print(heapq.heappop(heap))  # -> 1
print(heapq.heappop(heap))  # -> 3
print(heap)              # -> [5, 8]

Building from an existing list is one call:

import heapq

data = [9, 4, 7, 1, 8, 3, 5]
heapq.heapify(data)
print(data[0])           # -> 1
print(heapq.heappop(data))  # -> 1

Note that heap is just a list. heapq does not give you a special object; it maintains the heap property inside a normal list through its functions. If you mutate that list yourself with, say, heap.append(x), you break the invariant and the other functions will misbehave. Always go through heapq.

Cost of every operation

Every heap operation is either a single index lookup or one walk up or down the tree, and the tree’s height is about log n because the complete shape keeps it balanced. That is the whole cost story:

The two headline operations, push and pop, are O(log n) because doubling the number of items adds just one more level to the tree, hence one more possible swap. Peeking is free. Searching for something other than the minimum is no faster than a plain list, which is the price of not keeping everything sorted.

Min-heap versus max-heap

heapq only implements a min-heap: heappop always gives the smallest. Often you want the largest instead (highest priority, most expensive, top score). Python has no built-in max-heap, so the standard workaround is to store the negatives of your values. The smallest negative corresponds to the largest original value, so a min-heap over negatives behaves as a max-heap. Negate again on the way out to recover the real value.

import heapq

scores = [50, 20, 80, 10]
max_heap = []
for s in scores:
    heapq.heappush(max_heap, -s)   # store negatives

print(-max_heap[0])            # -> 80   (largest, peeked)
print(-heapq.heappop(max_heap))   # -> 80
print(-heapq.heappop(max_heap))   # -> 50

This trick works cleanly for numbers. For values you cannot simply negate, you can push tuples where the first element is a numeric priority you control.

Priority queues

A priority queue is the abstract idea a heap implements: a collection where you add items with a priority and always remove the one with the best priority, regardless of insertion order. (Contrast a plain queue, which removes items in the order they arrived.) A heap is the standard, efficient way to build a priority queue.

To attach a priority to an item, push a tuple (priority, item). Python compares tuples element by element, so it orders first by priority. The smallest priority comes out first.

import heapq

tasks = []
heapq.heappush(tasks, (2, "email the report"))
heapq.heappush(tasks, (1, "put out the fire"))
heapq.heappush(tasks, (3, "water the plants"))

print(heapq.heappop(tasks))   # -> (1, 'put out the fire')
print(heapq.heappop(tasks))   # -> (2, 'email the report')

One caution with tuples: if two priorities tie, Python moves on to compare the second tuple element. If those items are not comparable (for example, custom objects), that raises an error. A common fix is to insert a unique tie-breaker in the middle, such as a running counter, so the item itself is never compared:

import heapq

pq = []
counter = 0
for priority, name in [(1, "b"), (1, "a")]:
    heapq.heappush(pq, (priority, counter, name))
    counter += 1

print(heapq.heappop(pq))   # -> (1, 0, 'b')   (ties broken by insertion order)

Priority queues built on heaps are the engine inside many important algorithms: Dijkstra’s shortest-path algorithm, the A* search, Huffman coding for compression, and event-driven simulations that always process the next-earliest event.

Common pitfalls

• Assuming a heap is sorted. A heap only guarantees the root is the extreme value. The rest of the array is partially ordered, not sorted. If you need everything in order, pop repeatedly (that is O(n log n) and is essentially the heapsort algorithm) or use sorted().

• Mutating the list behind heapq’s back. heappush and heappop maintain the invariant. Appending, inserting, or assigning into the list directly can leave it in a state where heappop no longer returns the true minimum. Always use the module’s functions.

• Forgetting the child-bounds check when writing sift-down by hand. A node near the bottom may have zero or one child. Reading heap[2*i+1] without checking 2*i+1 < len(heap) reads past the end or grabs a stale element. Guard both child indices.

• Reaching for a max-heap that does not exist. heapq is min-only. Negate your numbers, or push a (negated_priority, item) tuple.

• Comparing items that are not comparable. When pushing tuples, a priority tie forces Python to compare the next element. If that element is a custom object with no ordering defined, you get a TypeError. Add a unique counter as a tie-breaker.

Practice

1. Write a function k_smallest(numbers, k) that returns the k smallest values from a list, using heapq.heapify once and then popping k times. State the time complexity of your approach.

2. Using the negation trick, write top_three(scores) that returns the three highest scores from a list of numbers, largest first.

3. By hand (on paper), start from the array [1, 3, 5, 4, 8, 9, 7], push the value 0, and write out the array after each swap of the sift-up. Confirm the final root is 0.