Python heapq: Priority Queues, Top N and Heaps Explained
Python heapq turns a plain list into a min-heap, giving you the smallest item instantly and fast pushes and pops. Learn how a heap is laid out, heappush, heappop and heapify, priority queues with tie-breakers, max heaps, top N and merging, with real timings.
- Python heapq works on ordinary lists and keeps the smallest item at index 0.
- Push and pop take O(log n) time; peeking at
heap[0]is O(1). - Getting the top 10 of a million numbers took 33.9 ms with
nsmallestversus 479.2 ms with a full sort. - Add a counter to
(priority, count, item)tuples, or equal priorities crash withTypeError.
Task schedulers, shortest-path algorithms, rate limiters, “top 10” leaderboards and event simulations all share one need: get the next most important item quickly while new items keep arriving. Sorting the list after every insert works but wastes time. Python heapq, a standard library module, solves it with a binary heap stored in a plain list.
All code below ran on Python 3.13.6 and the output is copied from the run. For the other built-in containers, see our Python collections guide.
What is a heap?
A heap is a binary tree with one rule: every parent is smaller than or equal to its children. That makes the root the smallest item in the whole tree. Unlike a sorted list, the rest of the tree is only partly ordered, which is exactly what makes inserts and removals cheap. Python’s heapq implements a min-heap; a max-heap keeps the largest item on top instead.
How heapq stores a heap in a list
There is no special heap class. The tree lives in a normal list where the children of index i sit at 2*i + 1 and 2*i + 2:
import heapq
h = []
for x in [5, 1, 8, 3, 9, 2]:
heapq.heappush(h, x)
print(h, h[0]) # [1, 3, 2, 5, 9, 8] 1
# 1
# / \
# 3 2
# / \ /
# 5 9 8
The list is not sorted: 3 comes before 2. But every parent is smaller than its children, and h[0] is always the minimum. Printing a heap and expecting sorted order is one of the most common heapq misunderstandings.
heappush and heappop
print([heapq.heappop(h) for _ in range(6)]) # [1, 2, 3, 5, 8, 9]
heappush(heap, item) appends the item and moves it up until the heap rule holds. heappop(heap) removes and returns the smallest item, moves the last item to the root and sifts it down. Each takes about log2(n) steps, so even a heap of a million items needs only around 20 comparisons per operation. Popping everything returns the items in sorted order, which is the idea behind heap sort.
heapify: turn a list into a heap
data = [5, 1, 8, 3, 9, 2]
heapq.heapify(data)
print(data) # [1, 3, 2, 5, 9, 8]
heapify rearranges an existing list in place in linear time, which is faster than pushing items one by one. Heapifying a list of one million random floats took 56.0 ms in our run. It returns None, so do not write data = heapq.heapify(data).
heappushpop and heapreplace
print(heapq.heappushpop(data, 0), data) # 0 [1, 3, 2, 5, 9, 8]
print(heapq.heapreplace(data, 7), data) # 1 [2, 3, 7, 5, 9, 8]
These combined operations are faster than a separate push and pop. The order differs, and the results show it:
heappushpoppushes first, then pops. Because 0 was smaller than everything, it came straight back out and the heap did not change.heapreplacepops first, then pushes. It returned the old minimum, 1, even though the new item 7 is bigger.
heappushpop is perfect for keeping a fixed-size “top K” heap while streaming data.
nlargest and nsmallest
scores = [71, 93, 55, 88, 99, 62, 80]
print(heapq.nlargest(3, scores)) # [99, 93, 88]
print(heapq.nsmallest(2, scores)) # [55, 62]
tasks = [{"name": "email", "p": 3}, {"name": "deploy", "p": 1}, {"name": "lint", "p": 2}]
print([t["name"] for t in heapq.nsmallest(2, tasks, key=lambda t: t["p"])])
# ['deploy', 'lint']
Both accept a key function, just like sorted. Use them when you need a few items out of many. When n is close to the full length, sorted() is simpler and just as quick, and for a single item use min() or max(). Our Python sort list guide covers key functions in depth.
Building a priority queue
Store tuples where the first element is the priority. Tuples compare element by element, so the lowest number comes out first:
pq = []
heapq.heappush(pq, (2, "write tests"))
heapq.heappush(pq, (1, "fix prod bug"))
heapq.heappush(pq, (3, "refactor"))
print([heapq.heappop(pq)[1] for _ in range(3)])
# ['fix prod bug', 'write tests', 'refactor']
The tie problem and the counter fix
When two priorities are equal, Python compares the next tuple element. If that is something without an ordering, such as a dict, it crashes:
heapq.heappush(pq, (1, {"job": "a"}))
heapq.heappush(pq, (1, {"job": "b"}))
# TypeError: '<' not supported between instances of 'dict' and 'dict'
The standard fix, recommended in the Python documentation, is a running counter as the second element:
import itertools
pq, counter = [], itertools.count()
for p, job in [(1, {"job": "a"}), (1, {"job": "b"}), (0, {"job": "c"})]:
heapq.heappush(pq, (p, next(counter), job))
print([heapq.heappop(pq)[2]["job"] for _ in range(3)]) # ['c', 'a', 'b']
The counter is unique, so the comparison never reaches the dict, and equal priorities come out in insertion order (a then b). That makes the queue stable and predictable. A dataclass with order=True and the payload field marked compare=False is another clean option.
Tip: always use the (priority, count, item) shape in production code, even if your items happen to be comparable today.
Max heaps
mh = []
for x in [5, 1, 8]:
heapq.heappush(mh, -x)
print([-heapq.heappop(mh) for _ in range(3)]) # [8, 5, 1]
On Python 3.13 and earlier, heapq has no public max-heap, so the usual trick is to store negated numbers. For non-numeric items, wrap them in a small class with a reversed __lt__. Python 3.14 adds public max-heap functions such as heappush_max and heappop_max. Our 3.13 test confirmed they are not available there, and we did not run them on 3.14.
Merging sorted data
print(list(heapq.merge([1, 4, 9], [2, 3, 10], [0, 5])))
# [0, 1, 2, 3, 4, 5, 9, 10]
heapq.merge lazily combines inputs that are already sorted, reading one item at a time from each. That makes it ideal for merging sorted log files or database exports that do not fit in memory, much like the lazy tools in our itertools guide.
Performance: heap vs sorting
We timed common jobs on one million random floats (best of three runs):
| Task | Time |
|---|---|
Top 10 with sorted(big)[:10] |
479.2 ms |
Top 10 with heapq.nsmallest(10, big) |
33.9 ms |
heapq.heapify on a copy of the list |
56.0 ms |
For a small n out of many items, nsmallest was about 14 times faster, because it only keeps a 10-item heap instead of sorting everything. The complexity summary:
| Operation | Cost |
|---|---|
Peek at smallest, h[0] |
O(1) |
heappush, heappop |
O(log n) |
heapify |
O(n) |
nsmallest(k, data) |
roughly O(n log k) |
| Search or remove an arbitrary item | O(n) |
Updating or removing a priority
heapq has no “decrease key” operation, and removing an item from the middle breaks the heap unless you re-heapify. The documented approach is lazy deletion: keep a dict from task to its heap entry, mark the old entry as removed when the priority changes, push a new entry, and skip removed entries when popping. This is how Dijkstra’s shortest-path algorithm is commonly written with heapq.
heapq vs other options
| Need | Use |
|---|---|
| Fast single-threaded priority queue | heapq |
| Queue shared between threads | queue.PriorityQueue (a locked wrapper around heapq) |
| Async producer and consumer | asyncio.PriorityQueue |
| Always-sorted collection with search | bisect on a list, or a sorted container library |
| First in, first out | collections.deque |
Common heapq mistakes
- Expecting
print(heap)to show sorted order. - Calling
list.sort()or appending directly, which can break the heap rule silently. - Forgetting the tie-breaker counter in priority tuples.
- Assigning the result of
heapify, which isNone. - Using heapq from several threads without a lock; use
queue.PriorityQueueinstead. - Using
nlargestto get one item;max()is simpler.
Final thoughts
Python heapq gives you a fast priority queue with nothing more than a list and a handful of functions. Push and pop in logarithmic time, read the minimum instantly, use nsmallest and nlargest for top N, and merge for sorted streams. Add a counter to break ties, negate values for a max-heap on older Pythons, and reach for queue.PriorityQueue when threads are involved. For more standard library power tools, see functools.
Frequently asked questions
Is Python heapq a min heap or a max heap?
heapq is a min heap, so index 0 always holds the smallest item. For a max heap on Python 3.13 and earlier, push negated numbers. Python 3.14 adds dedicated max heap functions.
Why is my heapq list not sorted?
A heap only guarantees that each parent is smaller than its children, not that the whole list is sorted. Pop items one by one, or call sorted on the list, to get full order.
How do I build a priority queue in Python?
Push tuples of priority, a counter and the item onto a list with heapq.heappush, then call heapq.heappop to get the item with the lowest priority number first.
What is the difference between heappushpop and heapreplace?
heappushpop pushes the new item first and then pops the smallest, so it can return the item you just pushed. heapreplace pops the smallest first and then pushes the new item.
Is heapq thread safe?
No. heapq functions do not use locks. For a priority queue shared between threads, use queue.PriorityQueue, which wraps heapq with locking.
Keep learning
Need help with testing, WordPress or SEO?
We help teams ship better software and grow their sites. Tell us what you are working on and we will suggest a clear next step.