1. Home
  2. Blog
  3. Software Development

Software Development

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.

9 min read
Python heapq: priority queues, top N and heaps explained

Key takeaways

  • 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 nsmallest versus 479.2 ms with a full sort.
  • Add a counter to (priority, count, item) tuples, or equal priorities crash with TypeError.

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:

  • heappushpop pushes first, then pops. Because 0 was smaller than everything, it came straight back out and the heap did not change.
  • heapreplace pops 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 is None.
  • Using heapq from several threads without a lock; use queue.PriorityQueue instead.
  • Using nlargest to 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

Work with Stack Quora

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.

Keep reading

More guides on testing, AI & modern development

Enjoyed this article? Pick a topic and jump straight into our newest tutorials.

Artificial Intelligence

K Nearest Neighbors (KNN) Explained: How It Works, With Python Code

K nearest neighbors explained: the KNN algorithm, a from-scratch NumPy version, choosing k, feature scaling, distance metrics, regression and vector…

Read article →
Software Development

HTTP Cookies Explained: Secure, HttpOnly, SameSite and Scope

HTTP cookies explained: Set-Cookie, Path, Domain, expiry, Secure, HttpOnly, SameSite, prefixes, deleting cookies and a secure session recipe, tested locally.

Read article →
DevOps

Git Rebase Interactive: Squash, Fixup, Reword and Autosquash

Git rebase interactive explained step by step: pick, reword, squash, fixup, edit, drop, autosquash, conflicts and undoing a rebase with…

Read article →
Software Testing

Alpha vs Beta Testing: Key Differences, Exit Criteria and Checklist

Alpha vs beta testing compared: who tests, what each phase finds, entry and exit criteria, how to run a beta,…

Read article →
Test Automation

Pytest Monkeypatch: 10 Tested Examples for Env Vars, Time and APIs

Pytest monkeypatch explained with 10 passing tests: environment variables, functions, config, time, sleeps, paths, blocking the network and the wrong-target…

Read article →
Databases & SQL

SQL Auto Increment: MySQL, PostgreSQL, SQL Server and SQLite

SQL auto increment in MySQL, PostgreSQL, SQL Server and SQLite: syntax, reading the new ID, why gaps appear, ID reuse,…

Read article →
Databases & SQL

SQL BETWEEN: Inclusive Ranges and the Date Trap Explained

SQL BETWEEN explained with tested queries: inclusive ranges, reversed bounds, NULLs, the last-day date trap, half-open ranges and index-friendly date…

Read article →
Software Development

JavaScript Template Literals: 10 Examples Including Tagged Templates

JavaScript template literals explained with 10 tested examples: interpolation, multiline strings, escaping, tagged templates for safe HTML and SQL, and…

Read article →
Software Development

Python heapq: Priority Queues, Top N and Heaps Explained

Python heapq explained: heappush, heappop, heapify, priority queues with tie-breakers, max heaps, nlargest and merge, with real timings against sorting.

Read article →
Software Development

Python Walrus Operator (:=) Explained With 8 Real Examples

The Python walrus operator := explained with 8 tested examples: if checks, regex matches, while loops, comprehensions, scope rules, precedence…

Read article →
Artificial Intelligence

Softmax Function Explained: Formula, Python Code and Stable Version

The softmax function explained: formula, worked example, NumPy code, the stable version that avoids NaN, temperature, cross-entropy and softmax vs…

Read article →
Software Development

CORS Explained: Preflight Requests, Headers and How to Fix CORS Errors

CORS explained: origins, simple and preflight requests, the response headers your server must send, credentials, and how to fix common…

Read article →
DevOps

Git Diff Explained: Staged Changes, Branches and Commits

Git diff explained: read the output, compare unstaged and staged changes, commits and branches, two dots vs three dots, and…

Read article →
Test Automation

Pytest Xdist: Run Tests in Parallel and Cut Test Time

Run pytest tests in parallel with pytest-xdist: install, the -n option, distribution modes, real timings and how to fix shared-state…

Read article →
Software Testing

Verification vs Validation in Software Testing: Example and Table

Verification vs validation in software testing explained with a comparison table and a tested coupon example where every spec test…

Read article →
Databases & SQL

SQL CAST Explained: Convert Data Types With Tested Examples

SQL CAST explained with tested examples: text to number, truncation, integer division, numbers stored as text, dates, bad input and…

Read article →
Databases & SQL

SQL DISTINCT: How to Remove Duplicate Rows (and Its Traps)

SQL DISTINCT explained with tested queries: one and many columns, NULLs, COUNT DISTINCT, DISTINCT vs GROUP BY, the SUM DISTINCT…

Read article →
Software Development

JavaScript Reduce Explained: 12 Practical Examples

JavaScript reduce explained step by step with 12 practical examples: sums, tallies, grouping, Maps, pipelines, sequential promises and the empty…

Read article →
Artificial Intelligence

Levenshtein Distance: Formula, Worked Table and Python Code

Levenshtein distance explained: the edit operations, the dynamic programming table for kitten and sitting, Python code with two-row memory, normalised…

Read article →
DevOps

Gitignore: Patterns, Negation and Fixing Tracked Files

A tested gitignore guide: pattern rules, leading and trailing slashes, negation with !, the ignored parent folder trap, git check-ignore…

Read article →
Software Testing

Acceptance Criteria: Given When Then Examples and Checklist

How to write acceptance criteria testers can run: rule-based and Given When Then formats, a worked discount code example turned…

Read article →
Software Testing

State Transition Testing: Diagram, Table and Example

State transition testing explained with a login lockout example: states, events, the diagram, the state table, valid and invalid transitions,…

Read article →
Databases & SQL

Second Highest Salary in SQL: 5 Tested Ways and the Tie Trap

Find the second highest salary in SQL five ways: MAX subquery, LIMIT OFFSET, DENSE_RANK, a correlated subquery and per department,…

Read article →
Databases & SQL

SQL ROW_NUMBER: Top N per Group, Dedupe and Pagination

SQL ROW_NUMBER explained with tested queries: PARTITION BY, top N per group, deleting duplicates, pagination, the tie trap and how…

Read article →
Test Automation

Python Unittest: Assert Methods, setUp and Mocks With Examples

A practical Python unittest tutorial: TestCase, assert methods, setUp and tearDown, subTest, skips, expected failures and mock, with a test…

Read article →
Artificial Intelligence

Jaccard Similarity: Formula, Python, MinHash

Jaccard similarity measures overlap between two sets as intersection over union. Work the formula, compute it in Python for words…

Read article →
DevOps

Git Hooks: Pre-commit and Commit-msg Examples

Git hooks run scripts at key moments such as commit and push. See tested pre-commit, commit-msg and prepare-commit-msg hooks, sharing…

Read article →
Test Automation

API Testing in Python: Pytest + Requests Suite

Build an API testing suite in Python with pytest and requests: fixtures, status codes, headers, JSON schema validation, CRUD flows,…

Read article →
Software Testing

Test Design Techniques: 9 Methods + Examples

Test design techniques help you write fewer tests that catch more bugs. Learn 9 black-box, white-box and experience-based methods with…

Read article →
Artificial Intelligence

TF-IDF Explained: Formula and Worked Example

TF-IDF scores a word by how often it appears in a document and how rare it is across all documents….

Read article →
DevOps

Git Tag: Create, Push and Delete Release Tags

Git tag explained with tested commands: annotated vs lightweight tags, listing and sorting, pushing with follow-tags, deleting local and remote…

Read article →
Test Automation

Pytest Coverage: pytest-cov and Branch Gaps

Measure pytest coverage with pytest-cov: term-missing reports, branch coverage, HTML reports, pyproject settings and a fail-under gate for CI, with…

Read article →
Software Testing

Error Guessing in Testing: Checklist + Demo

Error guessing uses tester experience to predict where code breaks. Get a ready checklist of risky inputs, a step by…

Read article →
Artificial Intelligence

BM25 Explained: How Keyword Search Ranks Results, With Python Code and Hybrid Search

BM25 explained with a pure Python implementation we ran: the formula, IDF, term saturation, the k1 and b parameters, why…

Read article →
DevOps

Git Bisect Explained: Find the Commit That Broke Your Code, Manually or Automatically

Git bisect explained with a tested repository: find the one bad commit among 41 in 5 test runs, automate it…

Read article →
Test Automation

pytest Markers Explained: Custom Marks, skip, skipif, xfail and -m Filters

pytest markers explained with a tested suite: register custom marks, run only smoke tests with -m, combine filters with and,…

Read article →