How does heapq work in Python?

Q: How does heapq work in Python?

**Target Audience:** Developers who have heard "use a heap for a priority queue" and want to know what `heapq` really does, up to candidates expected to explain the algorithm and its costs. **Difficulty:** Medium **Python version:** Behaviour checked on CPython 3.11 (python3.11 and the in-page Pyodide 0.25.1 runtime, which is CPython 3.11.3). The 3.14 max-heap functions are cited from the docs, not run. > **How to read this doc:** Each idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. Every output in the **Verified** section was copied from a real run of the examples on this page. ## 1. Why This Even Matters — A Story First Think of a hospital emergency room. Patients do not get seen in the order they arrive; the most urgent goes next. The triage nurse does not keep the whole waiting room in perfect order, though — that would mean re-sorting everyone each time someone walks in. They only need to

The problem

Question presented to candidate: "Python does not have a PriorityQueue class in the core containers, but it has heapq. How does it work? What data structure sits underneath, what do push and pop cost, and how would you use it to build a task scheduler or find the top k items?"

What a strong answer should cover:

heapq is a set of functions over a plain list kept as a binary min-heap: heap[k] <= heap[2k+1] and heap[k] <= heap[2k+2], so heap[0] is always the smallest. The list is not sorted.
Costs: heappush and heappop are O(log n), heap[0] is O(1), heapify is O(n); heappushpop and heapreplace combine a push and a pop in one sift.
Priority queues with (priority, counter, item) tuples: the counter breaks ties in FIFO order and stops Python from comparing the items; lazy deletion for cancelled entries.
nsmallest, nlargest and merge: top-k in O(n log k) and lazy merging of sorted inputs; sorted() or min() are better when k is large or 1.
Max-heaps: negate numeric keys on 3.11; Python 3.14 added public heappush_max, heappop_max, heapify_max and friends.
CPython detail: the C module _heapq replaces the Python code, only < is used, and heappop uses a "sift to a leaf, then back up" variant that saves comparisons.

Code / implementation expected: Yes — push and pop a few values, show the list is a heap and not sorted, and build a small priority queue with a tie-breaker.

heapq
data-structures

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Developers who have heard "use a heap for a priority queue" and want to know what heapq really does, up to candidates expected to explain the algorithm and its costs. Difficulty: Medium Python version: Behaviour checked on CPython 3.11 (python3.11 and the in-page Pyodide 0.25.1 runtime, which is CPython 3.11.3). The 3.14 max-heap functions are cited from the docs, not run.

How to read this doc: Each idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. Every output in the Verified section was copied from a real run of the examples on this page.

1. Why This Even Matters — A Story First

Think of a hospital emergency room. Patients do not get seen in the order they arrive; the most urgent goes next. The triage nurse does not keep the whole waiting room in perfec

The solution is hidden so you can try first

8 min read · 12 sections

Run the code

Edit the code and run it here. Each console line with an expected value becomes a test.

PythonThe heap invariant, push and pop, heapify, top-k, merge and a priority queue