Heaps with heapq

Reviewed & published by Brayan K

A heap is a tree-based structure that always keeps the smallest element ready at the front, and Python's heapq module turns an ordinary list into a binary min-heap so you can push and pop the minimum in fast O(log n) time.

Part of the free Python course at LearnCodingFast — hands-on lessons with examples you run in your browser, plus practice exercises and a quick quiz.

Heaps power priority queues, scheduling, and "top-k" queries. Once you see how heapq works, a whole class of problems becomes easy.

What You'll Learn in This Lesson

• Pushing and popping with heappush/heappop
• Turning a list into a heap with heapify
• Why a min-heap always pops the smallest
• Top-k queries with nlargest/nsmallest
• Priority queues using (priority, item) tuples
• The negation trick for a max-heap

1 heappush, heappop & heapify

A heap lives in a plain list. heappush adds an item keeping the heap valid, heappop always removes the smallest, and heapify rearranges an existing list into a heap in place:

import heapq

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

# The smallest is always at index 0
print(heap[0])              # 1

# heappop removes and returns the smallest each time
print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 3
print(heapq.heappop(heap))  # 5

# heapify turns any list into a heap in O(n), in place
nums = [9, 4, 7, 1, 2]
heapq.heapify(nums)
print(nums[0])              # 1  (smallest now at the front)

import heapq

# Heap-sort: push everything, pop everything
data = [9, 3, 5, 1, 8, 2]
heap = []
for x in data:
    heapq.heappush(heap, x)

ordered = [heapq.heappop(heap) for _ in range(len(heap))]
print(ordered)

# ✅ Expected output:
# [1, 2, 3, 5, 8, 9]

2 Top-k with nlargest & nsmallest

Need just the biggest or smallest few from a large collection? heapq.nlargest(k, data) and nsmallest(k, data) do it in O(n log k) — faster than a full sort when k is small. Both accept a key function just like sorted():

import heapq

scores = [88, 42, 71, 99, 63, 55, 100, 30]

# The 3 highest and 3 lowest
print(heapq.nlargest(3, scores))    # [100, 99, 88]
print(heapq.nsmallest(3, scores))   # [30, 42, 55]

# With a key, just like sorted()
people = [("Ada", 88), ("Ben", 42), ("Cleo", 99)]
top_two = heapq.nlargest(2, people, key=lambda p: p[1])
print(top_two)   # [('Cleo', 99), ('Ada', 88)]

For a million records where you only need the top 10, nlargest(10, data) keeps a heap of just 10 items as it scans once — far cheaper than sorting all million.

3 Priority Queues with Tuples

Push (priority, item) tuples and the heap orders by priority automatically, because Python compares tuples left to right. Add a tie-breaking counter so the heap never compares the items themselves:

import heapq
from itertools import count

pq = []
counter = count()   # 0, 1, 2, ... unique tie-breaker

# (priority, tie_breaker, task) — lower priority number = more urgent
heapq.heappush(pq, (2, next(counter), "email newsletter"))
heapq.heappush(pq, (1, next(counter), "fix production bug"))
heapq.heappush(pq, (3, next(counter), "tidy backlog"))
heapq.heappush(pq, (1, next(counter), "answer on-call page"))

while pq:
    priority, _, task = heapq.heappop(pq)
    print(f"[P{priority}] {task}")

# [P1] fix production bug
# [P1] answer on-call page
# [P2] email newsletter
# [P3] tidy backlog

import heapq

# Max-heap trick: negate values on the way in and out
nums = [3, 1, 4, 1, 5, 9, 2, 6]

max_heap = []
for n in nums:
    heapq.heappush(max_heap, -n)   # store negatives

# Pop the 3 LARGEST by un-negating
largest = [-heapq.heappop(max_heap) for _ in range(3)]
print(largest)

# ✅ Expected output:
# [9, 6, 5]

🎯 Your Turn: Fill in the Blanks

Replace each ___ so the code pushes tasks by priority and pops the most urgent first.

# 🎯 YOUR TURN: pop tasks in priority order
import heapq

pq = []
heapq.___(pq, (3, "low"))      # push onto the heap
heapq.heappush(pq, (1, "high"))
heapq.heappush(pq, (2, "medium"))

order = []
while pq:
    priority, name = heapq.___(pq)   # pop the smallest priority
    order.append(name)

print(order)

# Expected output:
# ['high', 'medium', 'low']

Common Errors

❌ Expecting the heap list to be sorted

heap = [5, 1, 8]
heapq.heapify(heap)
print(heap)   # [1, 5, 8] here, but NOT guaranteed fully sorted in general

✅ Pop repeatedly for sorted output

ordered = [heapq.heappop(heap) for _ in range(len(heap))]

❌ Tuples whose items can't be compared on a tie

heapq.heappush(pq, (1, {"a": 1}))
heapq.heappush(pq, (1, {"b": 2}))   # TypeError when priorities tie

✅ Add a unique tie-breaker

heapq.heappush(pq, (1, 0, {"a": 1}))
heapq.heappush(pq, (1, 1, {"b": 2}))   # safe

❌ Trying to pop the largest from a min-heap

heapq.heappop(heap)   # gives the SMALLEST, not the largest

✅ Negate values or use nlargest

biggest = heapq.nlargest(1, data)[0]

🎯 Mini Challenge: Merge Sorted Streams

heapq even has merge(), which lazily merges already-sorted inputs into one sorted stream — exactly how external merge sort works on huge files.

# 🎯 Mini Challenge: merge three sorted lists into one
import heapq

a = [1, 4, 7]
b = [2, 5, 8]
c = [3, 6, 9]

merged = list(heapq.merge(a, b, c))
print(merged)

# Also grab the 3 smallest overall in one call
print(heapq.nsmallest(3, merged))

# Expected output:
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
# [1, 2, 3]

📚 Keep Learning

• Python docs: heapq — Heap queue algorithm
• Python docs: Priority queue implementation notes
• Python docs: heap theory & properties

Frequently Asked Questions

Lesson complete — priority queues hold no fear!

You can push and pop the minimum with heappush/heappop, build a heap with heapify, grab the top-k with nlargest/nsmallest, build priority queues from tuples, and flip to a max-heap with the negation trick.

Practice quiz

Continue this course

• Previous: deque & Queues
• Next: Binary Search with bisect — Search and insert into sorted lists in O(log n) with bisect
• Quick reference: Python cheat sheet

Frequently asked questions

What is a heap and what is heapq?

A heap is a tree-shaped data structure that always keeps the smallest item instantly accessible at the front. Python's heapq module implements a binary min-heap directly on top of an ordinary list, so heapq.heappop() always removes and returns the smallest element in O(log n) time. It's the engine behind priority queues.

Is Python's heapq a min-heap or a max-heap?

It's always a min-heap: the smallest value sits at index 0 and pops out first. To get max-heap behaviour, push the negated values (-x) and negate again when you pop, or use heapq.nlargest(). There is no built-in max-heap, so the negation trick is the standard workaround.

How do I build a priority queue with heapq?

Push tuples of (priority, item) onto the heap. Python compares tuples element by element, so the lowest priority number pops first. If two priorities tie, add a unique counter as a second element — like (priority, count, item) — so the heap never has to compare the items themselves, which could raise a TypeError.

When should I use nlargest/nsmallest instead of sorting?

When you only need the top or bottom few from a large collection. heapq.nlargest(k, data) runs in O(n log k) and uses a heap of size k, whereas fully sorting the data is O(n log n). For k much smaller than n — like the top 10 from a million records — the heap approach is meaningfully faster and lighter on memory.