heapq in Python
Priority queues made easy.
Python's heap Q module turns an ordinary list into a heap. There's no special class. Just a handful of functions that keep the list in heap order.

- heapq module
- An ordinary list
- A few functions
An emergency room
Each patient is a tuple, of urgency and the problem. Smaller numbers are more urgent. Heap push adds a patient, and heap pop always removes the most urgent one, whatever order they arrived in. Run it. Urgency one is treated first, then two, then three.
import heapq
waiting = []
heapq.heappush(waiting, (3, "sprained ankle"))
heapq.heappush(waiting, (1, "heart attack"))
heapq.heappush(waiting, (2, "broken arm"))
heapq.heappush(waiting, (3, "cold"))
while waiting:
urgency, problem = heapq.heappop(waiting)
print(urgency, problem)1 heart attack 2 broken arm 3 cold 3 sprained ankle
heapq tips
Heapify turns an existing list into a heap in O of N. The smallest item is always at index zero. Heap Q is a min heap. For a max heap, store negative numbers. And tuples compare item by item, so the first value decides the priority, and the second breaks ties.
| key | value |
|---|---|
| heappush / heappop | O(log n) |
| heapify(list) | O(n) |
| heap[0] | peek the smallest |
| Max heap | push -value |
Summary
Heap Q gives you a priority queue on a plain list. Push and pop in O of log N, and the smallest is always at index zero. Next, a classic heap problem. The top K items.
Key takeaways- heappush
- heappop
- heap[0] is the smallest