heapq Module Fundamentals

Python's heapq module stores a heap inside an ordinary list. Every function takes the list as its first argument, and the order of the list's elements is the structure. The rule those functions maintain is the heap invariant: for every index i, heap[i] <= heap[2*i + 1] holds, and so does heap[i] <= heap[2*i + 2], wherever those children exist. That rule guarantees the smallest value sits at heap[0] and promises nothing about how the remaining values are ordered.

The list is a tree laid flat

Read the list as a binary tree stored level by level. Index 0 is the root, the children of index 1 sit at 3 and 4, and the children of index 2 sit at 5 and 6. A value is only ever compared with its own parent and children, so a valid heap can print in an order that looks unsorted. Run heapify on [5, 3, 8, 1, 9, 2], take the minimum off, then push a new value:

import heapq

nums = [5, 3, 8, 1, 9, 2]
heapq.heapify(nums)
print(nums)
print(nums[0])

smallest = heapq.heappop(nums)
print(smallest, nums)

heapq.heappush(nums, 4)
print(nums)

[1, 3, 2, 5, 9, 8]
1
1 [2, 3, 8, 5, 9]
[2, 3, 4, 5, 9, 8]

heapify rearranges the list in place to [1, 3, 2, 5, 9, 8] and returns None. The 2 at index 2 comes before the 5 at index 3, which is legal because index 3 is a child of index 1. heappop returns the 1. To fill the gap it puts the last element, the 8, at the root, and a sift-down swaps it past its smaller child, leaving [2, 3, 8, 5, 9]. heappush appends the 4 and sifts it up past its parent 8, giving [2, 3, 4, 5, 9, 8]. Each of those 2 calls walks a single root-to-leaf path, which is why each costs O(log n).

Building with heapify costs O(n), less than the O(n log n) of n separate pushes, because it sifts down from the last parent backward. Half the positions are leaves and never move, a quarter can drop at most 1 level, an eighth at most 2, and so on. That series adds up to at most about n level moves for the whole build.

Push-pop and replace run in opposite order

The 2 combined calls have similar names and different results. heappushpop pushes first, so a new item smaller than the root comes straight back and the heap is untouched. heapreplace pops first, so the old root always leaves, even when the new item is smaller.

import heapq

a = [2, 5, 7]
print(heapq.heappushpop(a, 1), a)

b = [2, 5, 7]
print(heapq.heapreplace(b, 1), b)

Either call can be the step of a top-K loop once the heap holds k items: heapreplace behind an if x > h[0] guard, or heappushpop alone, which runs that comparison internally. The bug to avoid is heapreplace with no guard, which evicts the root even when the new value is worse.

A max-heap by negation

heapq only builds min-heaps. To pop the largest value first, store every number negated, so the largest original becomes the smallest stored value, then negate again whenever a value comes out.

import heapq

scores = [40, 75, 12, 90]
max_heap = [-s for s in scores]
heapq.heapify(max_heap)

print(-max_heap[0])
print(-heapq.heappop(max_heap))
print(-max_heap[0])

2 failures to predict

Popping an empty heap raises IndexError: index out of range, the message from the C implementation of heappop. Reading h[0] on an empty list raises the list's own wording, IndexError: list index out of range. The second failure raises nothing at all: calling heappush or heappop on a list that was never heapified quietly returns the wrong value.

import heapq

h = [5, 1, 3]
heapq.heappush(h, 4)
print(heapq.heappop(h))

About this lesson

This section is part of the Heap & Top-K: Beginner lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.