Heaps with heapq
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.
The root is the minimum; the remaining list is not sorted
A heap is useful when new work keeps arriving and you repeatedly need the smallest priority. Its rule compares each parent with its children, not every neighboring pair in the list. Index zero is the minimum; taking a slice of the underlying list does not select the next few jobs in priority order.
import heapq
pending = [1, 4, 2, 7, 5, 3]
print("Minimum:", pending[0])
print("Already sorted:", pending == sorted(pending))
print("Removal order:", [heapq.heappop(pending) for _ in range(len(pending))])
print("After removal:", pending)
# ✅ Expected output:
# Minimum: 1
# Already sorted: False
# Removal order: [1, 2, 3, 4, 5, 7]
# After removal: []The comprehension fixes its number of iterations before it starts removing items. Popping repeatedly gives ordered values but consumes the heap. If you simply need a complete ordered copy once, use Sorting with sorted() & key.
import heapq
jobs = [7, 2, 5, 1]
result = heapq.heapify(jobs)
print("Return value:", result)
print("Minimum:", jobs[0])
heapq.heappush(jobs, 0)
print("New minimum:", heapq.heappop(jobs))
print("Remaining minimum:", jobs[0])
# ✅ Expected output:
# Return value: None
# Minimum: 1
# New minimum: 0
# Remaining minimum: 1heapify changes the list in place and returns None. It takes linear time to build the heap. Subsequent pushes and removals take logarithmic time; inspecting the root takes constant time. Do not append an arbitrary value or overwrite a priority directly and assume the heap rule survives.
import heapq
heapq.heappop([])
# ✅ Expected error:
# IndexError: index out of rangeTied priorities need a tie-breaker before the payload
Tuples compare field by field. A pair containing priority and a dictionary works until two priorities tie: Python then tries to compare the dictionaries. This makes a bug appear only for some data. The following failure uses two separate records with the same priority.
import heapq
pending = []
heapq.heappush(pending, (1, {"name": "Asha"}))
heapq.heappush(pending, (1, {"name": "Ben"}))
# ✅ Expected error:
# TypeError: '<' not supported between instances of 'dict' and 'dict'Store a unique arrival number between priority and payload. Because the arrival numbers differ, comparison stops there. It also makes equal-priority service follow arrival order. The heap itself does not provide stable ordering automatically.
import heapq
pending = []
arrivals = [(2, "Report"), (1, "Backup"), (1, "Invoice")]
for sequence, (priority, name) in enumerate(arrivals):
heapq.heappush(pending, (priority, sequence, {"name": name}))
while pending:
priority, sequence, job = heapq.heappop(pending)
print(priority, job["name"])
# ✅ Expected output:
# 1 Backup
# 1 Invoice
# 2 ReportSmaller priority numbers run first in this example; that is an application choice. If a larger numeric score should win, store its negative as the comparison key. Avoid modifying an entry already inside the heap; reconstruct and heapify after a small batch of edits, or design an explicit replacement strategy for a larger scheduler.
Pushing then popping is not the same as replacing the root
import heapq
keep_larger = [4, 7, 9]
replace_anyway = keep_larger.copy()
print("pushpop returned:", heapq.heappushpop(keep_larger, 2))
print("pushpop kept:", sorted(keep_larger))
print("replace returned:", heapq.heapreplace(replace_anyway, 2))
print("replace kept:", sorted(replace_anyway))
# ✅ Expected output:
# pushpop returned: 2
# pushpop kept: [4, 7, 9]
# replace returned: 4
# replace kept: [2, 7, 9]heappushpop retains the larger values in this min-heap, which is useful for keeping the best few scores. heapreplace removes the old minimum unconditionally, then inserts the new item; it can return a value larger than the newcomer. It also requires a nonempty heap. Choose the operation from the retention policy, not its shorter spelling.
import heapq
scores = [12, 7, 18, 10, 18]
print(heapq.nlargest(3, scores))
print(scores)
# ✅ Expected output:
# [18, 18, 12]
# [12, 7, 18, 10, 18]nlargest and nsmallest are convenient when the required result is small. For a complete ordered result, sorting is usually clearer. These examples use APIs present in Python 3.11 through 3.14; they do not depend on newer max-heap functions.
Complete a stable priority queue
Repair the two missing operations and the tuple field. Equal-priority entries must keep arrival order, and every printed result must come from a removal rather than a slice of heap storage.
import heapq
pending = []
for sequence, (priority, name) in enumerate([(2, "A"), (1, "B"), (1, "C")]):
heapq.___(pending, (priority, ___, name))
while pending:
priority, sequence, name = heapq.___(pending)
print(name)
# 👉 replace ___ with heappush
# 👉 replace ___ with sequence
# 👉 replace ___ with heappop
# ✅ Expected output:
# B
# C
# AKeep the three highest scores as results arrive
Consume scores 12, 7, 18, 10, 18 and 6 in that order. Keep at most three scores in a min-heap. Push until it has three entries, then use the combined push-and-pop operation for later arrivals. Print the retained scores in descending order and print the threshold, the smallest retained score. A duplicate score counts as a separate result.
import heapq
best = []
for score in [12, 7, 18, 10, 18, 6]:
if len(best) < 3:
heapq.heappush(best, score)
else:
heapq.heappushpop(best, score)
print("Best:", sorted(best, reverse=True))
print("Threshold:", best[0])
# ✅ Expected output:
# Best: [18, 18, 12]
# Threshold: 12The retained heap is ordered only when making the final report. The threshold remains available at the root throughout processing once the heap is full. An arrival queue with no priorities belongs to deque & Queues.
Practice quiz
What does this program print? import heapq h = [1, 4, 2, 7, 5, 3] print(h[0], h == sorted(h))
- 1 True
- 1 False
- 7 False
- 3 True
Answer: 1 False. A heap guarantees the minimum at the root, not a fully sorted list.
What does this program print? import heapq h = [4, 1, 3] print(heapq.heapify(h)) print(h[0])
- [1, 3, 4] 1
- 1 1
- None 4
- None 1
Answer: None 1. heapify mutates its argument and returns None.
What does this program print? import heapq h = [4, 7, 9] print(heapq.heappushpop(h, 2)) print(sorted(h))
- 2 [4, 7, 9]
- 4 [2, 7, 9]
- 2 [2, 7, 9]
- 9 [2, 4, 7]
Answer: 2 [4, 7, 9]. The smaller newcomer is returned and the larger entries stay.
What does this program print? import heapq h = [4, 7, 9] print(heapq.heapreplace(h, 2)) print(sorted(h))
- 2 [4, 7, 9]
- 9 [2, 4, 7]
- 4 [2, 7, 9]
- 4 [4, 7, 9]
Answer: 4 [2, 7, 9]. Replacement always removes the old root first.
What does this program print? import heapq h = [(1, 1, "B"), (1, 0, "A")] heapq.heapify(h) print(heapq.heappop(h)[2])
- A
- B
- 1
- 0
Answer: A. The unique sequence field breaks the priority tie before the name.
Which entry layout preserves arrival order for tied priorities and avoids comparing dictionaries?
- (priority, payload)
- (payload, priority)
- (priority, unique_sequence, payload)
- (priority, payload, unique_sequence)
Answer: (priority, unique_sequence, payload). The unique sequence must be compared before the payload.
What does this program print? import heapq values = [2, 8, 5] print(heapq.nlargest(2, values)) print(values)
- [2, 5] [2, 8, 5]
- [8, 5] [8, 5]
- [5, 8] [2, 8, 5]
- [8, 5] [2, 8, 5]
Answer: [8, 5] [2, 8, 5]. nlargest returns the chosen values without mutating the list.
Which error ends this program? import heapq heapq.heappop([])
- ValueError: empty heap
- IndexError: index out of range
- None
- KeyError: 0
Answer: IndexError: index out of range. Removing from an empty list heap raises IndexError.
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