Python heaps and priority queues
Remove the smallest priority efficiently.
On this page
Lists and tuples.
- Remove the smallest priority efficiently.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
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.
Code example
import heapq
tasks = [(3, "backup"), (1, "alert"), (2, "email")]
heapq.heapify(tasks)
while tasks:
priority, name = heapq.heappop(tasks)
print(priority, name)
assert tasks == []1 alert 2 email 3 backup
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
import heapq tasks = [(3, "backup"), (1, "alert"), (2, "email")]heapq.heapify(tasks)while tasks: priority, name = heapq.heappop(tasks) print(priority, name)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 |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
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.