The heapq module implements binary heaps on ordinary Python lists. A heap keeps the smallest item at index zero and supports insertion and removal in logarithmic time. This structure is useful for priority queues, shortest-path algorithms, scheduling, simulations, event processing, and selecting the largest or smallest values from a stream.
A heap is not a fully sorted list. Only the parent-child heap invariant is guaranteed. Iterating over the internal list does not produce ascending order. Use the module operations and treat the representation as an implementation detail.
Create an empty heap
A heap starts as a normal list.
import heapq
queue = []
heapq.heappush(queue, 5)
heapq.heappush(queue, 2)
heapq.heappush(queue, 8)
print(queue[0])
The smallest value is at queue[0], but the remaining positions are not fully ordered.
Remove the smallest item
heappop() removes and returns the smallest entry.
while queue:
print(heapq.heappop(queue))
Popping an empty heap raises IndexError. Check the condition or handle the expected case.
Build a heap with heapify
heapify() rearranges an existing list in linear time.
values = [9, 1, 7, 3, 2]
heapq.heapify(values)
This is more efficient than pushing every item individually when all data is already available.
Priority queues with tuples
Tuples compare field by field. A common pattern stores priority and payload.
queue = []
heapq.heappush(queue, (10, "report"))
heapq.heappush(queue, (1, "alarm"))
priority, task = heapq.heappop(queue)
Lower numbers leave first. For highest-priority-first behavior, negate numeric priorities or use max-heap APIs available in the target Python version.
Ties and stability
If priorities tie, Python compares the second tuple field. Non-comparable tasks may raise TypeError.
from itertools import count
counter = count()
heapq.heappush(queue, (priority, next(counter), task))
The counter also preserves insertion order among equal priorities.
Keep tasks out of comparisons
Domain objects, dictionaries, and callbacks should not participate in ordering.
Use (priority, sequence, item) or a dataclass whose comparison fields are explicitly controlled.
heappushpop
heappushpop() pushes one item and removes the smallest in one combined operation.
removed = heapq.heappushpop(heap, new_item)
It is efficient for maintaining the N largest values observed so far.
heapreplace
heapreplace() removes the smallest item first and then inserts the new one.
old = heapq.heapreplace(heap, new_item)
Its result differs from heappushpop() when the new item is smaller than the current root.
Keep the largest N values
Use a fixed-size min-heap.
limit = 100
heap = []
for value in stream:
if len(heap) < limit:
heapq.heappush(heap, value)
elif value > heap[0]:
heapq.heapreplace(heap, value)
The heap contains the largest values at the end, but they are not sorted.
nsmallest and nlargest
nsmallest() and nlargest() select extreme values.
top = heapq.nlargest(10, records, key=lambda item: item.score)
For small N relative to the input, these functions can beat sorting everything. When N is close to the total size, sorted() may be simpler and faster.
Key functions
The selection helpers accept key, while heappush() does not.
For a persistent heap, include the precomputed key in each tuple and avoid recalculating it during comparisons.
Merge sorted streams
heapq.merge() combines already sorted iterables lazily.
result = heapq.merge(file_a, file_b, key=extract_key)
for item in result:
process(item)
Every input must use the same ordering rule. The result does not load everything into memory.
Update priorities safely
The module has no direct decrease-key operation. Mutating an entry in place can break the heap invariant.
A safe strategy pushes a new entry and marks the old one as removed. Obsolete entries are skipped when popped.
REMOVED = object()
entries = {}
def add(item, priority):
if item in entries:
remove(item)
entry = [priority, next(counter), item]
entries[item] = entry
heapq.heappush(queue, entry)
def remove(item):
entry = entries.pop(item)
entry[2] = REMOVED
Pop valid entries
def pop_task():
while queue:
priority, sequence, item = heapq.heappop(queue)
if item is not REMOVED:
del entries[item]
return item
raise KeyError("empty priority queue")
Removed entries consume memory until they reach the root. Rebuild the heap periodically when updates are frequent.
Max-heaps
Traditional Python code represents a max-heap by negating numeric priorities.
heapq.heappush(queue, (-priority, sequence, item))
Do not negate non-numeric values. Also check the dedicated max-heap APIs available in the project’s minimum Python version.
Complexity
heappush() and heappop() are O(log n), reading the root is O(1), and heapify() is O(n).
These bounds do not include expensive key comparisons or large payload handling.
Graph algorithms
Priority queues appear in Dijkstra, A*, Prim, and event simulations.
Without decrease-key, push new distances and ignore stale entries when they are popped. Validate that Dijkstra edge weights are nonnegative.
Event scheduling
A heap can store (time, sequence, callback).
heapq.heappush(events, (when, next(counter), callback))
Use a monotonic clock for durations and never run long callbacks while holding a queue lock.
Threads
heapq does not synchronize access. Multiple threads require a lock or queue.PriorityQueue.
Python concurrent.futures can coordinate workers, but queue capacity and shutdown policy still matter.
Backpressure
An unlimited priority queue can grow until memory is exhausted.
Define capacity, rejection, persistence, or low-priority eviction. Consumers may not always keep up with producers.
Mutable priorities
If priority depends on an attribute that changes after insertion, ordering becomes invalid.
Store an immutable key and update by reinserting a new entry.
Get sorted output
Repeatedly pop items to preserve the heap process, or call sorted(heap) if the original heap is no longer needed.
Direct iteration over the internal list is not sorted output.
Persistence
The internal list can be serialized, but that exposes implementation details and obsolete entries.
Persist logical tasks and priorities, then reconstruct with heapify().
Security
External priorities can starve important work or monopolize capacity. Apply authorization, quotas, and service classes.
Never execute callbacks supplied by untrusted users.
Testing
Test empty queues, ties, negative priorities, updates, cancellation, removed entries, top-k logic, high volume, and concurrency.
Compare results with sorted() in property-based tests.
Common mistakes
Common failures include assuming the list is sorted, comparing non-comparable tasks, mutating priorities in place, confusing heapreplace() with heappushpop(), forgetting stable tie-breaking, and allowing unlimited growth.
Conclusion
heapq implements efficient priority queues on lists. Use tuples with a priority and sequence number, keep comparison keys immutable, and use lazy deletion for updates.
Consult the official heapq documentation, Python concurrent.futures, and the upcoming guide to bisect for ordered lists.
