Priority scheduling
Repeatedly select the next lowest-valued task while new tasks may arrive.
Python · Module
heapq
heapq provides a list-based priority queue using a min-heap. It supports efficiently adding items and retrieving the smallest item.
How it works
The heapq module stores values in a list arranged so the smallest item is at index 0. Use heapify to build that arrangement, heappush to add values, and heappop to remove the current minimum while preserving the heap invariant.
Syntax
heapq.heapify(x)
heapq.heappush(heap, item)
heapq.heappop(heap)
heapq.heappushpop(heap, item)
heapq.heapreplace(heap, item)Parameters
| Name | Type | Description |
|---|---|---|
x | list | List that is transformed into a heap in place. |
heap | list | Heap list receiving the new value. |
item | object | Value inserted into the heap. |
Returns
heapify returns None and changes the list in place; heappush returns None; heappop returns the smallest item.
Key points
- heapq supplies a priority-queue implementation based on heaps.
- A min-heap requires each parent value to be less than or equal to its children.
- Create an empty heap with a list, or convert existing data with heapify.
- heapify modifies the supplied list directly and takes linear time.
- heappush inserts an item without breaking the heap property.
- heappop returns the minimum and restores the heap arrangement.
Common mistakes
- Calling heappop on an empty heap raises IndexError; check the heap before removing an item.
- Reading heap[0] observes the minimum without changing the heap.
Example: Process jobs by priority
import heapq
jobs = [(2, "send email"), (1, "backup database"), (3, "refresh cache")]
heapq.heapify(jobs)
while jobs:
priority, name = heapq.heappop(jobs)
print(priority, name)Heapifies a list of priority-name pairs, then repeatedly removes the lowest-priority-number job.
When to use it
Top-n selection
Maintain the best or worst few values without fully sorting a large input.
Best-first traversal
Process graph or search frontier entries in increasing cost order.
Interview questions
QWhat does heapq provide?
heapq implements a priority-queue algorithm using a list-based min-heap. The smallest item is kept at index 0, while the remaining elements are only partially ordered.
Follow-up: How can an existing list become a heap efficiently? Call heapify; it transforms the list in place in linear time.
QHow do you add and remove values?
heappush adds an item while maintaining the min-heap invariant, and heappop removes and returns the smallest item while maintaining that invariant. Both operate on the heap list in place.
Follow-up: How would you inspect the next item without removal? Read heap[0].
QWhen should heapify be used?
heapify transforms a list into a min-heap in place and runs in linear time. It is suitable when starting with many existing values rather than inserting them individually.
Follow-up: What alternative creates an empty heap? Start with an empty list and add values using heappush.
Related
heapifyheappushheappopheappushpopheapreplacemergenlargestnsmallest