PYTHON / DATA STRUCTURES AND ALGORITHMS
Heaps and heapq
Use heapq to keep the smallest item of a growing collection reachable in O(1) and push/pop in O(log n), including max-heaps and top-k patterns.
What you will learn
- Read a plain list as a heap: parent at (i-1)//2, children at 2i+1 and 2i+2
- Use heappush, heappop, heapify, heappushpop and peek with heap[0]
- Get a max-heap by negating keys, since heapq is min-only
- Keep the top k of a stream with a size-k min-heap instead of sorting everything
Understanding Heaps and heapq
A binary heap is a complete binary tree stored flat in a list. The children of index i live at 2i+1 and 2i+2, and the parent of i is at (i-1)//2, so no pointers or node objects are needed; the arithmetic is the tree. heapq works directly on ordinary Python lists, which is why there is no Heap class to instantiate.
The only rule a heap enforces is that every parent compares less than or equal to both of its children. Siblings are completely unordered relative to each other, which means a heap is a partial order, not a sorted sequence. That weaker promise is exactly what makes it cheap: repairing the invariant after a push or a pop touches only one root-to-leaf path, so it costs O(log n) instead of the O(n) a sorted list would pay to shift elements.
heappop takes the root, moves the last element into the hole, then sifts it down by repeatedly swapping with its smaller child until the parent rule holds again. heappush appends at the end and sifts up towards the root. Because only the root is guaranteed minimal, heap[0] is a free peek but heap[-1] tells you nothing useful, and finding the maximum of a min-heap still requires scanning.
import heapq
tasks = [(5, 'email'), (1, 'deploy'), (3, 'review')]
heap = []
for t in tasks:
heapq.heappush(heap, t)
print(heap)
heapq.heappush(heap, (2, 'test'))
print(heap)
print(heap[0])
order = []
while heap:
order.append(heapq.heappop(heap))
print(order)A heap trades full sorted order for a single guarantee — parent <= children — and that partial order is what makes push and pop O(log n) with O(1) access to the minimum.
Worked examples
heapify in place and a max-heap by negation
Turns an existing list into a heap in linear time, then simulates a max-heap by storing negated keys.
import heapq
nums = [7, 2, 9, 4, 1, 8]
heapq.heapify(nums)
print(nums)
print(heapq.heappop(nums))
maxheap = [-n for n in [7, 2, 9, 4, 1, 8]]
heapq.heapify(maxheap)
print(-heapq.heappop(maxheap))
print(-heapq.heappop(maxheap))Example explained
Line 1heapify rearranges nums in place and returns None, so there is nothing to assign.
Line 2The result [1, 2, 8, 4, 7, 9] is a valid heap but not sorted: 8 sits before 4 because they are in different subtrees.
Line 3Negating every key flips the comparison, so the smallest negative is the largest original value.
Line 4Each pop must be negated again on the way out to recover the real number.
Top 3 of a stream with a size-3 heap
Keeps only the three largest values seen so far using a min-heap whose root is the weakest survivor.
import heapq
stream = [5, 1, 9, 3, 14, 7, 11]
k = 3
top = []
for x in stream:
if len(top) < k:
heapq.heappush(top, x)
elif x > top[0]:
heapq.heappushpop(top, x)
print(top)
print(sorted(top, reverse=True))Example explained
Line 1top[0] is the smallest of the three kept values, so it is the cheapest possible admission test.
Line 2heappushpop pushes then pops in one sift, cheaper than a separate push followed by a pop.
Line 3The heap never grows past k, so memory is O(k) even if the stream is huge.
Line 4The final list is unordered; sorting the three survivors at the end costs almost nothing.
Breaking priority ties without comparing payloads
Adds an increasing counter so equal priorities fall back to insertion order instead of comparing objects.
import heapq
from itertools import count
class Job:
def __init__(self, name):
self.name = name
counter = count()
pq = []
for prio, name in [(2, 'b'), (1, 'a'), (2, 'c')]:
heapq.heappush(pq, (prio, next(counter), Job(name)))
while pq:
prio, seq, job = heapq.heappop(pq)
print(prio, seq, job.name)Example explained
Line 1Tuples compare element by element, so the counter is only consulted when priorities are equal.
Line 2Job b was pushed first and wins the tie against Job c despite both having priority 2.
Line 3Without the counter, the tie would reach Job < Job and raise TypeError, since Job defines no ordering.
Important notes
heapq only implements a min-heap; there is no reverse or key parameter, so wrap or negate your keys instead.
heapq.nsmallest and nlargest are fine for small k, but for k close to n plain sorted() is usually faster.
Common mistakes
Treating the heap list as sorted and slicing heap[:3] for the three smallest items — only heap[0] is guaranteed, so the slice silently returns wrong values.
Pushing (priority, obj) where obj has no ordering; the moment two priorities tie, the comparison falls through to the objects and raises TypeError at runtime, often long after deployment.
Changing a stored item's priority in place (or calling heap.append) after it is in the heap; the parent rule is broken and heappop starts returning the wrong element with no error at all.
Try it yourself
Change, predict, then run
Given [12, 4, 7, 19, 3, 8, 1], heapify it and pop everything to print ascending order, then rewrite it with negated values so the same loop prints descending order.
Open the Python workspaceCheck your understanding
You have a min-heap stored in list h with 1000 items. What does it cost to find the largest element?
- O(n) — you must scan, because a min-heap says nothing about where the maximum sits beyond it being a leaf
- O(1) — the maximum is always h[-1], the last element of the list
- O(log n) — follow the larger child from the root down to the maximum
- O(1) — it is h[0] once heapify has been called
Show answer
The invariant only relates each parent to its own children, so the maximum can be any leaf and there are about n/2 leaves to check. h[-1] is tempting because the last element is a leaf, but nothing forces it to be the largest one; walking down from the root also fails, since a large value in one subtree tells you nothing about the other.