heapq Patterns in Python: Top-K and Dijkstra

Why This Matters

heapq is Python's standard priority queue tool. It is a min-heap, which makes the smallest priority cheap to retrieve without sorting all candidates every time.

Core Idea

Use heapq when the algorithm repeatedly needs the best next item.

Method	Role
`heapify`	turn a list into a heap in linear time
`heappush`	add a candidate
`heappop`	remove the smallest candidate
`heappushpop`	push and pop in one combined operation
`nlargest` / `nsmallest`	convenience top-k helpers

Non-Example or Failure Mode

heapq does not support decrease-key directly. Dijkstra implementations usually push a new pair and ignore a stale entry when it comes out of the heap.

Runnable Drill

heapq top-k and Dijkstra drill

Output will appear here.

Common Mistakes

Mistake	Correction
Forgetting that `heapq` is a min-heap.	Negate priorities or invert comparison data for max behavior.
Sorting the full input for small top-k.	Keep a size-`k` heap.
Failing to skip a stale entry in Dijkstra.	Compare popped distance with the current best distance.
Putting unorderable payloads in heap tuples after equal priorities.	Add a tie-breaker such as an incrementing counter.

Diagnostic Questions

Question type	Question	Answer signal
Definition	What does `heapq` expose?	A min-heap over a Python list.
Example / non-example	Does `heapq` have direct decrease-key?	No. Push a new priority and skip stale entries.
Computation	What is the push/pop cost?	O(log n).
Transfer	Why does Dijkstra use a heap?	It repeatedly needs the node with smallest tentative distance.

Exercises

Beginner:

Use heapify and heappop to sort a small list by repeated pops.
Keep the three largest values from a stream.
Simulate a task scheduler with (priority, task) pairs.

Intermediate:

Implement Dijkstra with stale-entry skipping.
Add a tie-breaker counter to a priority queue.

Challenge:

Compare full sorting vs heap top-k for k << n.

References

Python documentation. heapq: https://docs.python.org/3/library/heapq.html
Python documentation. Priority queue implementation notes: https://docs.python.org/3/library/heapq.html#priority-queue-implementation-notes