Python's heapq and bisect Modules: Priority Queues and Sorted Lists

Maria
Python
19 Sep, 2026

A lot of code needs data in order, but not always fully sorted all the time. A job scheduler only needs to know which task is most urgent right now. A leaderboard only needs the top ten. A pricing lookup needs to find which tier a value falls into. The obvious approach is to call sorted() or list.sort() whenever something changes, and that works until the list gets big or changes often.

Python's standard library has two small modules built for these situations. heapq turns a plain list into a binary heap, giving you a priority queue where the smallest item is always one step away. bisect performs binary search on a list that's already sorted, so you can find positions and insert new items without re-sorting.

This post covers both: how heaps work, building a proper priority queue, top-k and merge problems, binary search with bisect, the key parameter, and when to reach for something else. Examples run on Python 3.13.

Why Not Just Sort?

Here's the cost of the common operations with each approach:

Operation	Re-sort a list	`heapq`	`bisect` on a sorted list
Get the smallest item	O(1) after sort	O(1): `heap[0]`	O(1): `a[0]`
Remove the smallest	O(n) `pop(0)`	O(log n)	O(n) `pop(0)`
Add an item	O(n log n) re-sort	O(log n)	O(log n) search + O(n) insert
Find an item / position	O(n) scan	O(n) scan	O(log n)
Iterate in sorted order	Yes	No (must pop)	Yes

The pattern: use a heap when you repeatedly need the minimum (or maximum) while adding items, and use bisect when you need fast lookups in data that's kept sorted.

heapq: Binary Heaps on Plain Lists

A min-heap is a list arranged so that heap[k] <= heap[2*k + 1] and heap[k] <= heap[2*k + 2] for every index. The consequence is that heap[0] is always the smallest item. The rest of the list is only partially ordered, which is what makes adding and removing so cheap.

heapq doesn't define a heap class. Its functions operate on a regular list that you own:

from heapq import heappop, heappush

h = []
for n in [5, 1, 8, 3, 2]:
    heappush(h, n)

print(h, h[0])
print([heappop(h) for _ in range(len(h))])

[1, 2, 8, 5, 3] 1
[1, 2, 3, 5, 8]

Notice the list itself isn't sorted ([1, 2, 8, 5, 3]), but the smallest item is at the front, and popping repeatedly yields items in ascending order. Each push and pop is O(log n).

Because a heap is just a list, two rules apply: only modify it through heapq functions (an append() or sort() breaks or wastes the heap structure), and use heap[0] to peek without removing.

heapify: Turning an Existing List into a Heap

If you already have the data, heapify() rearranges it in place in O(n) time, which is faster than pushing items one by one:

from heapq import heapify, heappop

nums = [9, 4, 7, 1, 8, 2]
heapify(nums)
print(nums)
print(heappop(nums), nums)

[1, 4, 2, 9, 8, 7]
1 [2, 4, 7, 9, 8]

heappushpop and heapreplace

These combine a push and a pop into one, more efficient operation. They differ in order:

from heapq import heappushpop, heapreplace

h = [1, 3, 5]
print(heappushpop(h, 0), h)   # push first, then pop: returns 0, heap unchanged
print(heappushpop(h, 4), h)   # push 4, pop the smallest (1)

h = [1, 3, 5]
print(heapreplace(h, 0), h)   # pop first, then push: returns 1 even though 0 is smaller

0 [1, 3, 5]
1 [3, 4, 5]
1 [0, 3, 5]

heapreplace is the one you want for fixed-size heaps, where you always remove one item for each one you add.

Building a Priority Queue

The textbook use of a heap is a priority queue: tasks go in with a priority, and you always take the most urgent one out next. Tuples compare element by element, so (priority, item) pairs order themselves by priority:

from heapq import heappop, heappush

tasks = []
heappush(tasks, (2, "write tests"))
heappush(tasks, (1, "fix prod bug"))
heappush(tasks, (3, "update docs"))

while tasks:
    priority, name = heappop(tasks)
    print(priority, name)

1 fix prod bug
2 write tests
3 update docs

The Tie-Breaking Problem

That works until two items share a priority and the items themselves can't be compared. Then Python falls through to comparing the second element of the tuple:

t = []
heappush(t, (1, {"name": "a"}))
heappush(t, (1, {"name": "b"}))
# TypeError: '<' not supported between instances of 'dict' and 'dict'

Even when items are comparable, falling back to them means equal-priority tasks come out in an arbitrary order (alphabetical by name, say) instead of first-in, first-out.

The standard fix is to put a monotonically increasing counter between the priority and the item. The counter is unique, so the comparison never reaches the item, and ties come out in insertion order:

import itertools
from heapq import heappop, heappush
from typing import Any


class PriorityQueue:
    def __init__(self) -> None:
        self._heap: list[tuple[int, int, Any]] = []
        self._counter = itertools.count()

    def push(self, item: Any, priority: int) -> None:
        heappush(self._heap, (priority, next(self._counter), item))

    def pop(self) -> Any:
        priority, _, item = heappop(self._heap)
        return item

    def __len__(self) -> int:
        return len(self._heap)


pq = PriorityQueue()
pq.push({"job": "email"}, 2)
pq.push({"job": "resize"}, 1)
pq.push({"job": "report"}, 2)

while pq:
    print(pq.pop())

{'job': 'resize'}
{'job': 'email'}
{'job': 'report'}

"email" and "report" share priority 2 and come out in the order they were added.

Using a Dataclass Instead of Tuples

If you prefer named fields, a dataclass with order=True works too. Exclude the payload from comparisons with field(compare=False):

import itertools
from dataclasses import dataclass, field
from heapq import heappop, heappush


@dataclass(order=True)
class Job:
    priority: int
    seq: int
    name: str = field(compare=False)
    payload: dict = field(compare=False, default_factory=dict)


counter = itertools.count()
jobs: list[Job] = []
heappush(jobs, Job(2, next(counter), "email"))
heappush(jobs, Job(1, next(counter), "resize"))
print(heappop(jobs).name)   # resize

order=True generates comparison methods that compare fields in definition order, skipping any marked compare=False.

Max-Heaps

heapq is a min-heap. On Python 3.13 and earlier, the common trick for a max-heap is to negate numeric priorities:

from heapq import heappop, heappush

maxh = []
for n in [5, 1, 8, 3]:
    heappush(maxh, -n)

print(-heappop(maxh), -maxh[0])   # 8 5

For the priority queue above, push (-priority, next(counter), item) to make higher numbers more urgent. Python 3.14 adds dedicated max-heap functions (heapify_max(), heappush_max(), heappop_max(), and friends), so on 3.14+ you no longer need the negation trick.

Changing a Task's Priority

Heaps don't support efficient lookup, so you can't find a task and change its priority in place. The usual approach, described in the heapq docs, is lazy deletion: keep a dict from task to its heap entry, mark the old entry as removed, push a new entry, and skip removed entries when popping. If you need this often, it's a sign you might want a different structure.

What About queue.PriorityQueue?

queue.PriorityQueue is a thread-safe wrapper around heapq with blocking get() and put(). Use it when producer and consumer threads share the queue. In single-threaded code, or with asyncio (which has its own asyncio.PriorityQueue), plain heapq is simpler and faster.

Top-k Problems: nlargest and nsmallest

To get the k largest or smallest items, you don't need to sort everything:

from heapq import nlargest, nsmallest

scores = [72, 95, 88, 61, 99, 84]
print(nlargest(3, scores), nsmallest(2, scores))

products = [
    {"name": "mug", "price": 12},
    {"name": "lamp", "price": 65},
    {"name": "pen", "price": 1},
    {"name": "desk", "price": 240},
]
print(nlargest(2, products, key=lambda p: p["price"]))

[99, 95, 88] [61, 72]
[{'name': 'desk', 'price': 240}, {'name': 'lamp', 'price': 65}]

Both accept a key function, like sorted(). Which one to use depends on k relative to n:

k = 1: use min() or max().
k small compared with n: nlargest / nsmallest. They keep a heap of only k items, so they run in roughly O(n log k).
k close to n: sorted(data)[:k] is faster.

The real win is on streams. Because nlargest only holds k items, it works on an iterator of millions of rows without loading them into memory. Here's the same idea written out, which is useful when you want to keep the top k up to date as data arrives:

from collections.abc import Iterable
from heapq import heappush, heapreplace


def top_k(stream: Iterable[int], k: int) -> list[int]:
    heap: list[int] = []
    for x in stream:
        if len(heap) < k:
            heappush(heap, x)
        elif x > heap[0]:
            heapreplace(heap, x)   # drop the smallest of the current top k
    return sorted(heap, reverse=True)


print(top_k(iter([5, 1, 9, 3, 7, 6, 8, 2]), 3))   # [9, 8, 7]

A min-heap of size k holds the k largest values seen so far. Its smallest element, heap[0], is the bar a new value has to beat.

Merging Sorted Streams with merge

heapq.merge() combines several already-sorted inputs into one sorted output, lazily:

from heapq import merge

print(list(merge([1, 4, 9], [2, 3, 10], [0, 5])))

logs1 = [("09:00", "a"), ("09:05", "b")]
logs2 = [("09:01", "c"), ("09:07", "d")]
print(list(merge(logs1, logs2, key=lambda e: e[0])))

[0, 1, 2, 3, 4, 5, 9, 10]
[('09:00', 'a'), ('09:01', 'c'), ('09:05', 'b'), ('09:07', 'd')]

It only holds one item from each input at a time, so you can merge several huge sorted log files by timestamp without reading them into memory. Pass reverse=True if the inputs are sorted in descending order. Chunked external sorting (sort pieces that fit in memory, write them out, then merge) is built on exactly this function.

A Classic: Dijkstra's Shortest Path

Heaps are the engine behind many graph algorithms. Dijkstra's algorithm repeatedly expands the closest unvisited node, which is exactly "pop the minimum":

from heapq import heappop, heappush


def dijkstra(graph: dict[str, list[tuple[str, int]]], start: str) -> dict[str, int]:
    dist = {start: 0}
    heap = [(0, start)]
    while heap:
        d, node = heappop(heap)
        if d > dist.get(node, float("inf")):
            continue   # stale entry: we already found a shorter path
        for nxt, weight in graph[node]:
            nd = d + weight
            if nd < dist.get(nxt, float("inf")):
                dist[nxt] = nd
                heappush(heap, (nd, nxt))
    return dist


g = {"A": [("B", 4), ("C", 1)], "B": [("D", 1)], "C": [("B", 2), ("D", 5)], "D": []}
print(dijkstra(g, "A"))

{'A': 0, 'B': 3, 'C': 1, 'D': 4}

The continue line is the lazy deletion idea from earlier: instead of updating an entry's priority, push a new one and ignore outdated ones when they surface.

bisect: Binary Search on Sorted Lists

bisect answers one question very quickly: where would this value go in a sorted list? It uses binary search, so it takes O(log n) comparisons. On a million items, that's about 20.

bisect_left vs bisect_right

The two functions differ only in how they handle values equal to the target:

from bisect import bisect_left, bisect_right

xs = [10, 20, 20, 20, 30, 40]

print(bisect_left(xs, 20), bisect_right(xs, 20))
print(bisect_left(xs, 25), bisect_right(xs, 25))

1 4
4 4

bisect_left returns the position before any existing equal values (index 1).
bisect_right (also available as plain bisect) returns the position after them (index 4).
When the value isn't present, both return the same insertion point.

That difference is useful on its own. bisect_right(xs, 20) - bisect_left(xs, 20) is the number of 20s in the list (3), counted in O(log n).

Membership and Range Queries

bisect doesn't tell you whether a value is present, but it's a one-line check:

from bisect import bisect_left, bisect_right


def contains(a: list[int], x: int) -> bool:
    i = bisect_left(a, x)
    return i < len(a) and a[i] == x


def count_in_range(a: list[int], lo: int, hi: int) -> int:
    """Count items with lo <= item <= hi."""
    return bisect_right(a, hi) - bisect_left(a, lo)


print(contains(xs, 30), contains(xs, 35))   # True False
print(count_in_range(xs, 15, 30))           # 4

For one-off membership tests on unsorted data, a set is still faster (O(1) on average). bisect wins when you also need ordering, ranges, or nearest values.

Nearest Value Lookups

Finding the largest item less than or equal to x, or the smallest item greater than or equal to x, is a frequent need ("what's the closest earlier snapshot?"):

def find_le(a, x):
    """Rightmost value <= x."""
    i = bisect_right(a, x)
    if i:
        return a[i - 1]
    raise ValueError(f"no value <= {x}")


def find_ge(a, x):
    """Leftmost value >= x."""
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError(f"no value >= {x}")


print(find_le(xs, 25), find_ge(xs, 25))   # 20 30

Mapping Values to Buckets

A neat use of bisect is turning a list of breakpoints into a lookup table. Grade boundaries are the classic example:

from bisect import bisect_right


def grade(score: int, breakpoints=(60, 70, 80, 90), grades="FDCBA") -> str:
    return grades[bisect_right(breakpoints, score)]


print([grade(s) for s in [33, 60, 77, 89, 90, 100]])

['F', 'D', 'C', 'B', 'A', 'A']

The same shape works for tax brackets, shipping tiers, and "which price was in effect on this date":

from bisect import bisect_right
from datetime import date

effective = [date(2026, 1, 1), date(2026, 4, 1), date(2026, 9, 1)]
prices = [10.0, 12.0, 15.0]


def price_on(day: date) -> float:
    i = bisect_right(effective, day) - 1
    if i < 0:
        raise ValueError("no price before the first effective date")
    return prices[i]


print(price_on(date(2026, 3, 31)), price_on(date(2026, 4, 1)), price_on(date(2026, 12, 25)))
# 10.0 12.0 15.0

This replaces a chain of if/elif comparisons with a data table that's easy to update.

Keeping a List Sorted with insort

insort inserts a value at the correct position so the list stays sorted:

from bisect import insort

ys = [1, 3, 5]
insort(ys, 4)
insort(ys, 0)
insort(ys, 6)
print(ys)   # [0, 1, 3, 4, 5, 6]

Finding the spot is O(log n), but inserting into a Python list is O(n) because later items have to shift. For a few thousand items that's still very fast (the shift is a single memory move). For large lists with frequent inserts, see the section on alternatives below.

The key Parameter (Python 3.10+)

All bisect functions accept a key function, so you can search lists of records sorted by a field:

import bisect

events = [(1, "a"), (5, "b"), (9, "c")]   # sorted by timestamp

print(bisect.bisect_left(events, 5, key=lambda e: e[0]))   # 1
bisect.insort(events, (7, "x"), key=lambda e: e[0])
print(events)

1
[(1, 'a'), (5, 'b'), (7, 'x'), (9, 'c')]

There's an asymmetry to be aware of: for bisect_left and bisect_right, the key is applied to the list items but not to the value you're searching for, so you pass the bare key (5), not a record. For insort, the key is applied to the new item as well, so you pass the full record. Mixing these up is a common source of TypeError.

The list must be sorted by that same key. bisect never checks; on an unsorted list it silently returns meaningless positions. To search a descending list, use a key that reverses the order, such as key=lambda v: -v for numbers, and negate the search value too.

When to Use Something Else

Sorted collection with many inserts and deletes: the third-party sortedcontainers package provides SortedList, SortedDict, and SortedSet, with fast inserts, deletes, and index lookups on large data. It's pure Python and widely used.
FIFO queue without priorities: use collections.deque, which has O(1) appends and pops on both ends. See the collections module.
Fast membership only: use a set or dict.
Priority queue shared between threads: use queue.PriorityQueue.
Data sorted once, then read: just call sorted() and use bisect for lookups.

Conclusion

heapq and bisect are both small modules that operate on ordinary lists, and both replace "sort it again" with something much cheaper. Reach for heapq when you repeatedly need the smallest or largest item while adding new ones: priority queues (with a counter to break ties), top-k on large streams, merging sorted inputs, and graph algorithms. Reach for bisect when your data is already sorted and you need positions, counts, nearest values, or bucket lookups in O(log n).

Keep the invariants in mind and they'll stay reliable: only touch a heap through heapq functions, and only use bisect on lists sorted by the same key you search with.