Python heapq: Heap Queue Algorithm
What you’ll learn
Section titled “What you’ll learn”- The min-heap invariant and why
heap[0]is always the smallest. heappush,heappop,heapify, and their complexities.nsmallest/nlargestfor top-N without a full sort.- How to build a max-heap by negating values.
- When
heapqbeats a sorted list and whenqueue.PriorityQueueis the better choice.
Summary
Section titled “Summary”heapq implements a binary min-heap on top of a plain list. There is no heap class — just functions (heappush, heappop, heapify, nsmallest, nlargest) that maintain the heap-order invariant on a list you pass in. The smallest element is always at index 0, and heappop removes and returns it in O(log n). It is the standard tool for priority queues and for “top N” problems where you repeatedly extract the smallest (or largest) items as the collection changes.
The problem it solves
Section titled “The problem it solves”Repeatedly finding and removing the smallest item from a plain list means re-sorting or re-scanning every time: list.sort() is O(n log n) and pop(0) is O(n). For a priority queue or a scheduler that pulls the next item constantly, that is wasteful. A heap gives O(log n) push and pop, so the smallest is always one O(1) peek away and extraction is O(log n). For top-N, nlargest/nsmallest avoid sorting the entire input — getting the top 3 of a million items does not require sorting all million.
How it works
Section titled “How it works”The min-heap invariant
Section titled “The min-heap invariant”heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] — each parent is no greater than its children. So heap[0] is always the smallest. The rest is not fully sorted; only the invariant holds.
import heapq
tasks = [(5, "low"), (1, "urgent"), (3, "medium")]heapq.heapify(tasks) # O(n) rearrange in placeprint(tasks[0]) # (1, 'urgent')heapq.heappush(tasks, (2, "high"))print(heapq.heappop(tasks)) # (1, 'urgent') -- always the smallest, O(log n)print(heapq.heappop(tasks)) # (2, 'high')Core functions
Section titled “Core functions”heappush(heap, item): add an item, O(log n).heappop(heap): remove and return the smallest, O(log n).heapify(x): rearrange an existing list into heap order, O(n) — faster thannseparateheappushcalls, which is O(n log n).heappushpop/heapreplace: combined push-then-pop, slightly more efficient than the separate calls.nsmallest(n, iterable)/nlargest(n, iterable): return the n smallest or largest without sorting everything; for smallnrelative to the input size this beats a full sort.
Max-heap via negation
Section titled “Max-heap via negation”heapq is a min-heap only. To get a max-heap, negate the keys on the way in and out:
import heapq
max_heap = []for value in [5, 1, 9, 3]: heapq.heappush(max_heap, -value)print(-heapq.heappop(max_heap)) # 9 -- the largestFor tuples, negate the priority: (-priority, item).
Tie-breaking tuples
Section titled “Tie-breaking tuples”When heap items are tuples, comparison falls through element by element. (1, "urgent") versus (1, "also urgent") compares the strings next. If the second element is not comparable (for example, two dicts), it raises TypeError. The fix is a tie-breaker that is always comparable, often a counter:
from itertools import countimport heapq
tie = count()heapq.heappush(q, (priority, next(tie), item))Result shape and edge cases:
heap[0]is the smallest, but the rest is not sorted. Do not assumeheap[1]is the second smallest.heapifyis O(n); pushing items one at a time is O(n log n). Preferheapifywhen you already have the initial list.heappopon an empty heap raisesIndexError.nlargest/nsmallestwithnclose to the input size are no faster thansorted(...)— they win whennis small.
Realistic example
Section titled “Realistic example”OrdersPortal needs a priority queue of orders to fulfill (lower number = higher priority) and a “top 3 largest orders” report.
import heapqfrom itertools import count
class FulfillmentQueue: def __init__(self): self._heap = [] self._tie = count() # stable order for equal priorities
def add(self, order_id, priority): # priority 1 = urgent; tie-breaker keeps insertion order heapq.heappush(self._heap, (priority, next(self._tie), order_id))
def next_order(self): if not self._heap: raise IndexError("no orders to fulfill") priority, _, order_id = heapq.heappop(self._heap) return order_id, priority
q = FulfillmentQueue()q.add("ORD-1001", priority=3) # normalq.add("ORD-1002", priority=1) # urgentq.add("ORD-1003", priority=2) # highq.add("ORD-1004", priority=1) # urgent, but later than ORD-1002
print(q.next_order()) # ('ORD-1002', 1)print(q.next_order()) # ('ORD-1004', 1) -- tie broken by insertion orderprint(q.next_order()) # ('ORD-1003', 2)Top-3 largest orders without sorting all of them:
import heapq
orders = [ ("ORD-1001", 250.00), ("ORD-1002", 80.50), ("ORD-1003", 1999.99), ("ORD-1004", 430.00), ("ORD-1005", 75.25), ("ORD-1006", 1200.00),]
top3 = heapq.nlargest(3, orders, key=lambda o: o[1])print(top3)# [('ORD-1003', 1999.99), ('ORD-1006', 1200.0), ('ORD-1004', 430.0)]A max-heap of order amounts (negate the keys):
import heapq
amounts = [250.00, 80.50, 1999.99, 430.00]max_heap = [-a for a in amounts]heapq.heapify(max_heap)print(-heapq.heappop(max_heap)) # 1999.99 -- largest firstProduction patterns
Section titled “Production patterns”- Use a counter tie-breaker (
itertools.count) so equal-priority items never compare their payload — avoidsTypeErrorand keeps FIFO order. - For a priority queue consumed across threads, use
queue.PriorityQueue, which wraps a heap and adds locking, blockingget, and task tracking. - Use
heapifyto build the heap from an existing list in O(n), not repeatedheappush. - For top-N over a stream, use
nlargest/nsmallest, or maintain a size-N heap withheappushpopto keep only the N largest seen so far. - Store
(priority, tiebreaker, item)tuples; never rely on comparing the item object itself.
Common mistakes
Section titled “Common mistakes”- Assuming the heap is fully sorted after
heapify— only the invariant holds;heap[0]is the smallest, nothing more. - Forgetting a tie-breaker and hitting
TypeErrorwhen two items have equal priority and the payload is not comparable. - Using
heappopon an empty heap —IndexError. - Building the heap with
nheappushcalls when you already have the list — useheapify(O(n) vs O(n log n)). - Using
heapqfor “smallest so far” when you actually need the full sorted order — justsorted(). - Negating values for a max-heap but forgetting to negate again on the way out.
When to use it and when not to
Section titled “When to use it and when not to”Use heapq when:
- You need a priority queue or scheduler that repeatedly extracts the smallest item.
- You need the top-N (or bottom-N) of a large collection without a full sort.
- You maintain a bounded “largest N seen” over a stream.
Avoid heapq when:
- You need a fully sorted list —
sorted()is simpler and as fast for one-shot ordering. - You need blocking, thread-safe queue semantics — use
queue.PriorityQueue(it wraps a heap). - You need indexed or middle access — a heap is not an ordered list.
Compatibility
Section titled “Compatibility”heapq is in the standard library and available on Python 3.9 through 3.14 (and far older). heappush, heappop, heapify, nsmallest, nlargest, heappushpop, and heapreplace are all supported. No third-party packages are required.
Interview questions
Section titled “Interview questions”-
What is the time complexity of
heapq.heappop(), and what does the heap guarantee after it? O(log n). Afterheappop, the heap invariant still holds —heap[0]is the next smallest — but the list is not fully sorted; only each parent is no greater than its children. -
Is
heapqa min-heap or a max-heap, and how do you get the other behavior? A min-heap —heap[0]is always the smallest. For a max-heap, negate the keys on the way in and out:heappush(h, -value), then-heappop(h). For tuples, negate the priority:(-priority, item). -
Why use
nsmallest/nlargestinstead ofsorted()for top-N? They avoid a full sort:nlargest(k, data)uses a size-k heap and is O(n log k), which beatssorted(data)[-k:]at O(n log n) when k is small relative to n. When k is close to n,sorted()is about as fast and simpler. -
Senior scenario: a priority queue of orders works in tests but intermittently raises
TypeError: '<' not supported between instances of 'Order'in production. What is happening and how do you fix it robustly? Two orders with the same priority madeheapqcompare the second tuple element — theOrderobjects — andOrderhas no ordering defined, so<fails. Tests missed it because the test data never had two equal-priority items. The robust fix is a tie-breaker that is always comparable and preserves insertion order: push(priority, next(counter), order)wherecounteris anitertools.count(). Comparisons then never reach theOrderobject. Alternatively, giveOrdera__lt__that compares by a stable key, but the counter tie-breaker is the standard, least-surprising approach and keeps FIFO order for equal priorities.
Key takeaways
Section titled “Key takeaways”heapqis a min-heap on a plain list;heap[0]is always the smallest.heappush/heappopare O(log n);heapifyis O(n).nsmallest/nlargestgive top-N without a full sort.- For a max-heap, negate the keys on the way in and out.
- Use a counter tie-breaker to avoid comparing payloads and keep FIFO order; use
queue.PriorityQueuefor thread-safe blocking semantics.
Related pages
Section titled “Related pages”- collections —
dequeand other container building blocks - OrderedDict — when you need ordered, not priority, access
- itertools —
count()for tie-breakers and other iterator tools - threading vs multiprocessing — concurrency and
queue.PriorityQueue