Skip to content

Python heapq: Heap Queue Algorithm

  • The min-heap invariant and why heap[0] is always the smallest.
  • heappush, heappop, heapify, and their complexities.
  • nsmallest/nlargest for top-N without a full sort.
  • How to build a max-heap by negating values.
  • When heapq beats a sorted list and when queue.PriorityQueue is the better choice.

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.

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.

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 place
print(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')
  • 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 than n separate heappush calls, 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 small n relative to the input size this beats a full sort.

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 largest

For tuples, negate the priority: (-priority, item).

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 count
import 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 assume heap[1] is the second smallest.
  • heapify is O(n); pushing items one at a time is O(n log n). Prefer heapify when you already have the initial list.
  • heappop on an empty heap raises IndexError.
  • nlargest/nsmallest with n close to the input size are no faster than sorted(...) — they win when n is small.

OrdersPortal needs a priority queue of orders to fulfill (lower number = higher priority) and a “top 3 largest orders” report.

import heapq
from 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) # normal
q.add("ORD-1002", priority=1) # urgent
q.add("ORD-1003", priority=2) # high
q.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 order
print(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 first
  • Use a counter tie-breaker (itertools.count) so equal-priority items never compare their payload — avoids TypeError and keeps FIFO order.
  • For a priority queue consumed across threads, use queue.PriorityQueue, which wraps a heap and adds locking, blocking get, and task tracking.
  • Use heapify to build the heap from an existing list in O(n), not repeated heappush.
  • For top-N over a stream, use nlargest/nsmallest, or maintain a size-N heap with heappushpop to keep only the N largest seen so far.
  • Store (priority, tiebreaker, item) tuples; never rely on comparing the item object itself.
  • 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 TypeError when two items have equal priority and the payload is not comparable.
  • Using heappop on an empty heap — IndexError.
  • Building the heap with n heappush calls when you already have the list — use heapify (O(n) vs O(n log n)).
  • Using heapq for “smallest so far” when you actually need the full sorted order — just sorted().
  • Negating values for a max-heap but forgetting to negate again on the way out.

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.

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.

  1. What is the time complexity of heapq.heappop(), and what does the heap guarantee after it? O(log n). After heappop, 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.

  2. Is heapq a 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).

  3. Why use nsmallest/nlargest instead of sorted() for top-N? They avoid a full sort: nlargest(k, data) uses a size-k heap and is O(n log k), which beats sorted(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.

  4. 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 made heapq compare the second tuple element — the Order objects — and Order has 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) where counter is an itertools.count(). Comparisons then never reach the Order object. Alternatively, give Order a __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.

  • heapq is a min-heap on a plain list; heap[0] is always the smallest.
  • heappush/heappop are O(log n); heapify is O(n).
  • nsmallest/nlargest give 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.PriorityQueue for thread-safe blocking semantics.