Python heaps and priority queues
Remove the smallest priority efficiently.
Python
import heapq
tasks = [(3, "backup"), (1, "alert"), (2, "email")]
heapq.heapify(tasks)
while tasks:
priority, name = heapq.heappop(tasks)
print(priority, name)
assert tasks == []Output
1 alert 2 email 3 backup
Explanation
A min-heap keeps the smallest item at index zero, but the rest of the backing list is not fully sorted. heappop restores the heap invariant after removing the minimum.
Tuple priorities compare lexicographically. Here numeric priority is compared first and the label breaks equal-priority ties.
Explore the dry run
Guided walkthroughReady
1
import heapq2
3
tasks = [(3, "backup"), (1, "alert"), (2, "email")]4
heapq.heapify(tasks)5
while tasks:6
priority, name = heapq.heappop(tasks)7
print(priority, name)8
assert tasks == []Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Create three priority-label pairs. | priorities = [3, 1, 2] | — | |
| Reorganize in place to satisfy the min-heap invariant. | minimum = (1, alert) | — | |
| Remove priority 1. | remaining priorities = {2, 3} | — | |
| Print the first task. | remaining priorities = {2, 3} | 1 alert | |
| Remove priority 2 next. | remaining priorities = {3} | 1 alert | |
| Print the second task. | remaining priorities = {3} | 1 alert 2 email | |
| The final iteration removes and prints backup. | tasks = [] | 1 alert 2 email 3 backup |
Cost and common mistakes
O(n) heapify, O(log n) per pop, O(n log n) to remove all items. The heap stores O(n) items.
- Popping an empty heap raises IndexError.
- Equal priorities with non-comparable payloads need a comparable tie-breaker such as an insertion counter.
Try it yourself
Add (0, 'urgent') before heapify.
Reveal answer and reasoning
urgent is printed first because 0 is the smallest priority.