Python’s heapq Module

A heap is a tree-shaped data structure that keeps one specific element — usually the smallest — instantly accessible at the top, no matter how many other elements sit below it. Python’s heapq module gives you this behavior for free: it turns an ordinary list into a binary min-heap using a handful of functions, so you never have to write the tree logic yourself. It’s the engine behind priority queues, task schedulers, Dijkstra’s shortest-path algorithm, and any “give me the next best item” problem. This lesson covers every public function in heapq, why it achieves the complexity it does, and the mistakes that trip up nearly everyone the first time they use it.

Overview: What heapq Gives You

A binary heap is a complete binary tree — every level is fully filled except possibly the last, which fills left to right — that obeys the heap-order property: every parent node is less than or equal to both of its children (for a min-heap). That single rule guarantees the smallest element in the entire tree always sits at the root, so reading it is O(1). Because the tree is complete, it can be stored implicitly in a plain array with no pointers at all: for a node at index i, its children live at indices 2*i + 1 and 2*i + 2, and its parent lives at index (i - 1) // 2. This is exactly what heapq does — a “heap” in Python is just a regular list that you only ever modify through heapq‘s functions, which restore the heap-order property after every change.

Picture an emergency room: patients need to be treated in order of severity, not arrival order, and new patients keep walking in. A sorted list would need an O(n) insertion (shifting elements) to stay sorted; a heap gives you O(log n) insertion and O(1) access to “who’s most urgent right now” without ever fully sorting the collection. That’s the whole point of a heap — it sacrifices full ordering (the rest of the list is not guaranteed sorted) in exchange for making the one operation you care about, “give me the extreme element,” cheap and repeatable.

Unlike Java’s PriorityQueue or C++’s priority_queue, heapq is not a class. There is no Heap object to instantiate. You keep your own list and pass it into free functions such as heapq.heappush(heap, item), which mutate that list in place.

Function	What it does
heapq.heappush(heap, item)	Adds item and re-sifts to restore the heap property.
heapq.heappop(heap)	Removes and returns the smallest item, then re-sifts.
heapq.heapify(x)	Reorders an existing list x in place into a valid heap.
heapq.heappushpop(heap, item)	Pushes item, then pops and returns the smallest — one sift instead of two.
heapq.heapreplace(heap, item)	Pops and returns the smallest, then pushes item — assumes the heap is non-empty.
heapq.merge(*iterables)	Lazily merges already-sorted iterables into one sorted iterator.
heapq.nlargest(n, iterable, key=None)	Returns the n largest items, sorted descending.
heapq.nsmallest(n, iterable, key=None)	Returns the n smallest items, sorted ascending.

heappushpop and heapreplace look similar but differ in order of operations. heappushpop pushes first, so if the new item happens to be the smallest, it’s returned immediately without ever entering the heap — more efficient when that’s likely. heapreplace pops first, so it can return a value smaller than the item you’re pushing, and it will raise IndexError if the heap is empty. Because heapq only ever gives you the minimum, getting a max-heap requires a trick: negate every number going in, and negate again coming out. That trick is covered in depth in the examples below.

Time and Space Complexity

All of heapq‘s per-item operations run in time proportional to the height of the tree, which is O(log n) for n elements, because the tree is complete and therefore balanced by construction — there’s no way for it to degenerate into a long chain the way an unbalanced binary search tree can.

Operation	Time	Why
heapq.heappush	O(log n)	New item starts as a leaf and “sifts up,” swapping with its parent at most once per level — at most log n levels.
heapq.heappop	O(log n)	The last leaf moves to the root and “sifts down,” swapping with the smaller child at most once per level.
heap[0] (peek)	O(1)	The heap-order property guarantees the minimum is always at index 0.
heapq.heapify	O(n)	Building bottom-up, most nodes are near the leaves and need little or no sifting; the work sums to a linear, not linearithmic, total.
heapq.nlargest / nsmallest	O(n log k)	Internally maintains a heap of size k while scanning all n items, instead of sorting everything.
heapq.heapreplace / heappushpop	O(log n)	One sift-down after the swap, same reasoning as push/pop.

The O(n) cost of heapify surprises a lot of people, since pushing n items one at a time costs O(n log n) — you’d expect building the whole thing to cost the same. The difference is where the work happens. In a heap of n elements, roughly half the nodes are leaves that need zero sift work, a quarter are one level up and need at most one swap, an eighth need at most two swaps, and so on. Summing (number of nodes at height h) × h across all heights converges to a constant multiple of n, not n log n, because the expensive high-swap-count work only ever happens to a tiny number of nodes near the root. This is why you should always prefer heapq.heapify(existing_list) over pushing elements one by one when you already have all your data.

Space is O(n) to store the heap itself, since it’s just a Python list — no extra pointer or node overhead the way a linked tree structure would need. nlargest/nsmallest use O(k) auxiliary space for their internal bounded heap.

Examples

Example 1: Basic Heap Operations

This example builds a heap from an unordered list, pushes a new smallest value, and pops the minimum.

import heapq

def basic_heap_demo() -> list[int]:
    numbers = [5, 1, 8, 3, 9, 2]
    heapq.heapify(numbers)
    print('Heap after heapify:', numbers)

    heapq.heappush(numbers, 0)
    print('Heap after pushing 0:', numbers)

    smallest = heapq.heappop(numbers)
    print('Popped smallest:', smallest)
    print('Heap after pop:', numbers)

    return numbers

basic_heap_demo()

Output:

Heap after heapify: [1, 3, 2, 5, 9, 8]
Heap after pushing 0: [0, 3, 1, 5, 9, 8, 2]
Popped smallest: 0
Heap after pop: [1, 3, 2, 5, 9, 8]

heapify rearranges [5, 1, 8, 3, 9, 2] in place into a valid (though not sorted) array where every parent is ≤ its children. Pushing 0 appends it as a new leaf and sifts it all the way up to the root, since it’s smaller than everything. Popping removes and returns that root (0), moves the last leaf into the root’s spot, and sifts it down — landing back on the same array the heap started with, since we simply added and removed the same value.

Example 2: A Priority Queue with Tuples

The idiomatic way to build a priority queue in Python is a heap of tuples: (priority, item). Tuple comparison compares the first elements first, falling back to the second only when the first elements tie.

import heapq

def schedule_tasks() -> None:
    tasks: list[tuple[int, str]] = []
    heapq.heappush(tasks, (3, 'write report'))
    heapq.heappush(tasks, (1, 'fix critical bug'))
    heapq.heappush(tasks, (2, 'review pull request'))
    heapq.heappush(tasks, (1, 'answer support ticket'))

    while tasks:
        priority, task = heapq.heappop(tasks)
        print(f'Priority {priority}: {task}')

schedule_tasks()

Output:

Priority 1: answer support ticket
Priority 1: fix critical bug
Priority 2: review pull request
Priority 3: write report

Lower numbers pop first, so priority 1 tasks come out before priority 3. Notice the two priority-1 tasks: 'answer support ticket' comes out before 'fix critical bug' even though it was pushed after it. That’s because when priorities tie, heapq falls back to comparing the strings, and 'answer...' sorts before 'fix...' alphabetically. This is a common surprise — see Common Mistakes below for what happens when the second tuple element isn’t comparable at all.

Example 3: Top-K Elements, the Manual Way and the Easy Way

Since heapq only gives you a min-heap, finding the k largest values normally means negating everything on the way in and out. heapq.nlargest/nsmallest do this internally so you don’t have to.

import heapq

def compare_approaches() -> None:
    scores = [42, 17, 89, 5, 63, 91]

    max_heap = [-score for score in scores]
    heapq.heapify(max_heap)
    manual_top_three = [-heapq.heappop(max_heap) for _ in range(3)]

    builtin_top_three = heapq.nlargest(3, scores)
    builtin_bottom_three = heapq.nsmallest(3, scores)

    print('Manual top 3:', manual_top_three)
    print('heapq.nlargest top 3:', builtin_top_three)
    print('heapq.nsmallest bottom 3:', builtin_bottom_three)

compare_approaches()

Output:

Manual top 3: [91, 89, 63]
heapq.nlargest top 3: [91, 89, 63]
heapq.nsmallest bottom 3: [5, 17, 42]

The manual approach negates every score, builds a min-heap of the negatives, and pops three times — the most negative value corresponds to the largest original value, so negating the popped results gives [91, 89, 63]. heapq.nlargest(3, scores) reaches the identical answer without any negation, because it manages the sign flip internally. Both agree, which is exactly the point: reach for nlargest/nsmallest in real code and save the manual trick for when you need a live, mutable max-heap rather than a one-shot top-k query.

How heapq Works Step by Step

To see the “sift-up” mechanism concretely, trace what happens when you push the values 5, 3, 8, 1, 9, 2 one at a time into an initially empty heap. After each push, the new item starts at the end of the list (as a leaf) and is swapped with its parent for as long as it’s smaller than that parent.

Push	Heap array after insertion	What happened
5	[5]	First element; nothing to compare against.
3	[3, 5]	3 is less than its parent 5, so they swap; 3 becomes the root.
8	[3, 5, 8]	8’s parent is 3; 8 is not less than 3, so it stays put.
1	[1, 3, 8, 5]	1 is less than its parent 5, swap; then less than the new parent 3, swap again; 1 reaches the root.
9	[1, 3, 8, 5, 9]	9’s parent is 3; 9 is not less than 3, so it stays put.
2	[1, 3, 2, 5, 9, 8]	2 is less than its parent 8, swap; then compared to the new parent 1, 2 is not less than 1, so it stops there.

Each swap moves the new item up exactly one level, and there are at most log n levels, which is where the O(log n) push cost comes from. Notice the final array, [1, 3, 2, 5, 9, 8], is a valid heap (every parent ≤ its children) but is clearly not a fully sorted list — 5 sits before 9 and 8 even though it’s smaller than both. That’s the tradeoff: O(1) access to the minimum, in exchange for giving up on the ordering of everything else.

Common Mistakes

Mistake 1: Assuming heapq Is a Max-Heap

The single most common heapq bug is expecting heappop to return the largest item. It always returns the smallest.

import heapq

numbers = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(numbers)
largest = heapq.heappop(numbers)  # WRONG: heapq is a min-heap, this pops the smallest
print(largest)

Output:

1

The variable is named largest, but heappop has no idea about that intent — it just returns the root, which is always the minimum (1 here), not the maximum (9). The fix is the negation trick from Example 3: push the negated values, and negate again on the way out.

import heapq

def get_largest(numbers: list[int]) -> int:
    max_heap = [-number for number in numbers]
    heapq.heapify(max_heap)
    return -heapq.heappop(max_heap)

values = [3, 1, 4, 1, 5, 9, 2, 6]
print(get_largest(values))

Output:

9

Mistake 2: Ties Between Non-Comparable Second Elements

A (priority, item) tuple only avoids comparing item when priorities never tie. The moment two priorities are equal, heapq falls back to comparing the second elements — and if those aren’t comparable with <, you get a runtime TypeError, not a compile-time warning.

import heapq

tasks = []
heapq.heappush(tasks, (2, {'name': 'task A'}))
heapq.heappush(tasks, (2, {'name': 'task B'}))

Output:

Traceback (most recent call last):
    ...
TypeError: '<' not supported between instances of 'dict' and 'dict'

Both priorities are 2, so the heap tries to compare the two dictionaries with < to decide their order — and dictionaries don’t support ordering comparisons at all. The standard fix is to add a unique, always-comparable tiebreaker (an incrementing counter works well) as the second element, so the comparison never reaches the unorderable payload.

import heapq
import itertools

def schedule_with_tiebreak() -> None:
    counter = itertools.count()
    tasks = []
    heapq.heappush(tasks, (2, next(counter), {'name': 'task A'}))
    heapq.heappush(tasks, (2, next(counter), {'name': 'task B'}))

    while tasks:
        priority, _, task = heapq.heappop(tasks)
        print(priority, task['name'])

schedule_with_tiebreak()

Output:

2 task A
2 task B

Because the counter values (0 and 1) are always distinct, the comparison stops at the second tuple element and never touches the dictionaries, while also preserving insertion order among equal priorities as a side effect.

Best Practices

• If you only need the minimum or maximum of a collection once, use min()/max() — O(n) and simpler. Reach for a heap only when you need the extreme value repeatedly as the collection changes.
• Build a heap from existing data with heapq.heapify() in O(n) rather than looping and calling heappush n times, which costs O(n log n).
• For priority queues, use (priority, tiebreaker, item) tuples with an itertools.count() tiebreaker whenever item might not be orderable, or whenever priorities can plausibly tie.
• For a max-heap, negate numeric priorities going in and out rather than trying to write a custom comparator — heapq has no way to flip its comparison direction.
• Prefer heapq.nlargest(k, ...) / nsmallest(k, ...) over sorted(iterable)[:k] when you only need a handful of extreme elements from a large collection — O(n log k) beats O(n log n).
• Never mutate the heap list directly with append, sort, or item deletion outside of heapq‘s functions — doing so silently breaks the heap-order property, and later pushes/pops will return wrong results with no error raised.
• heapq has no built-in way to change an item’s priority or remove an arbitrary item in O(log n). The standard workaround, used in real Dijkstra implementations, is lazy deletion: push a new entry with the updated priority, leave the stale one in place, and skip stale entries when they’re popped (commonly by checking a visited/seen set).

Practice Exercises

• Merge k sorted lists. Given several already-sorted lists of integers, produce one fully sorted list containing all their elements. Try it two ways: using heapq.merge() directly, and by hand with a heap of (value, list_index, element_index) tuples. Hint: the tuple form needs a tiebreaker for equal values, same as Mistake 2 above.
• Running median. Process a stream of numbers one at a time and print the median after each one, using two heaps: a max-heap for the smaller half of the numbers seen so far, and a min-heap for the larger half, keeping their sizes balanced within one element. For the stream 5, 15, 1, 3, the medians after each insertion should be 5, 10.0, 5, 4.0.
• Earliest-arrival scheduler. Given a list of (arrival_time, task_name) pairs, always process the earliest arrival first, breaking ties alphabetically by task_name. For input [(2, 'B'), (1, 'C'), (1, 'A')], the processing order should be A, C, B. Hint: this is exactly the tuple-comparison behavior from Example 2 — no extra tiebreaker needed since strings are always comparable.

Summary

• heapq turns a plain Python list into a binary min-heap; for a node at index i, children sit at 2*i + 1 and 2*i + 2, and the minimum is always at index 0.
• heappush and heappop are O(log n) because they sift along the height of the tree; peeking heap[0] is O(1).
• heapq.heapify() builds a heap from unordered data in O(n), not O(n log n) — prefer it over repeated pushes when you already have all the data.
• There is no max-heap variant: negate numeric values going in and out to simulate one.
• Tuple-based priority queues compare later tuple elements only when earlier ones tie — add a unique tiebreaker (e.g. itertools.count()) whenever the payload might not be orderable.
• heapq.nlargest(k, ...)/nsmallest(k, ...) solve top-k problems in O(n log k), avoiding a full O(n log n) sort.
• A heap only guarantees the root is extreme — the rest of the underlying list is not fully sorted.