Skip to content
Tutorials Center
My learning

Topics

Lesson 107 of 225 ยท Heaps

Heaps in Python: heapq

Use Python's heapq module: heappush, heappop, heapify, nlargest, nsmallest, merge, max-heaps, tuple priorities, tie-breaking counters and custom objects.

You just built a binary heap from scratch. In real Python code you almost never do that again, because the standard library ships a fast, well-tested one: the heapq module. It is a min-heap that works directly on an ordinary list, so there is no Heap class to learn. You keep a list, and heapq functions maintain the heap property inside it.

This lesson covers every function you need, the tricks for max-heaps, priorities stored as tuples, the tie-breaking counter that saves you from confusing errors, and how to put your own objects in a heap. It also compares heapq with queue.PriorityQueue from the priority queues lesson.

The basics: heappush, heappop, heapify

A heap in heapq is just a list. You start with an empty list, or any list you hand to heapify.

Function What it does Time
heappush(heap, x) add x O(log n)
heappop(heap) remove and return the smallest O(log n)
heap[0] peek at the smallest (no function needed) O(1)
heapify(lst) turn a list into a heap, in place O(n)
heappushpop(heap, x) push x, then pop the smallest, in one step O(log n)
heapreplace(heap, x) pop the smallest, then push x, in one step O(log n)
Python heappush, heappop and heapify

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two things to remember. The list is not sorted: only heap[0] is guaranteed to be the minimum. And functions like sorted(heap) or heap.sort() are still available, but treat the list as a heap only through heapq. Modifying it directly, for example with heap.append(x), silently breaks the heap property.

heappushpop versus heapreplace

They look alike but differ in order:

  • heappushpop(heap, x) pushes first, then pops. The result is never larger than x. If x is smaller than everything, it returns x right away without touching the heap.
  • heapreplace(heap, x) pops first, then pushes. It returns the old minimum, even if x is smaller, and it raises IndexError on an empty heap.

Both save a sift compared with calling push and pop separately. heappushpop is the key to the size-k heap technique.

nlargest, nsmallest and merge

Sometimes you do not need a heap object at all, just a result.

  • heapq.nsmallest(k, iterable, key=None) returns the k smallest items, sorted ascending.
  • heapq.nlargest(k, iterable, key=None) returns the k largest items, sorted descending.
  • heapq.merge(*sorted_iterables, key=None) merges already-sorted inputs lazily, returning an iterator.
Python nlargest, nsmallest and merge

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Choosing between nsmallest, sorted()[:k] and min:

  • For k = 1, use min() or max(). They are the fastest.
  • For small k and large n, nlargest and nsmallest run in about O(n log k) time using a size-k heap. They use only O(k) extra memory, and they work on a stream you can only read once.
  • When k is close to n, sorted(data)[:k] at O(n log n) is simpler and as fast or faster.

Notice that the nlargest(2, students, key=...) call returned Ana before Dev, even though both scored 91: ties keep their original order, just like a stable sort.

Max-heaps

heapq is a min-heap, so there are two ways to get the largest item first.

Python 3.14 and newer adds true max-heap functions: heapify_max, heappush_max, heappop_max, heappushpop_max and heapreplace_max. They work on a list that is kept in max-heap order. Do not mix the two families on the same list. This course runs Python 3.14, so you can use them here, but code that must run on older versions needs the trick below.

The classic trick for all versions is to store the negative of each number. The smallest negative is the largest original value. Negate on the way in and again on the way out.

Python Max-heap: negation trick and Python 3.14 functions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Tuples as priorities

Real tasks have both a priority and a payload. Python compares tuples element by element, from the left, so (priority, item) pairs sort by priority first:

Python A task queue with tuple priorities

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the two priority-1 tasks. They came out in alphabetical order ("answer..." before "fix..."), not in the order they were added, because on a tie Python moves on to comparing the second tuple element, the strings. That is rarely what you want, and it gets worse when the second element cannot be compared at all.

The tie-breaking counter

If two entries have equal priorities and the payloads are not comparable (dictionaries, custom objects without ordering), heapq raises TypeError. The standard fix is a third tuple element: an increasing counter. It breaks every tie, so the payload is never compared, and it makes equal priorities come out in first-in, first-out order.

Python Comparing payloads fails without a counter (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The count() object from itertools gives 0, 1, 2, ... forever. The result is a stable priority queue: among equal priorities, the one pushed earlier is served first.

Custom objects

You can also put your own class in a heap if it defines __lt__ (heapq only uses <). A dataclass(order=True) generates all comparisons from the fields in order. Use field(compare=False) to exclude fields from the comparison:

Python Custom objects with dataclass ordering

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Changing or removing items: lazy deletion

A heap cannot find an arbitrary item quickly, so there is no heap.remove(x) that is fast (list.remove followed by heapify costs O(n)). The common solution is lazy deletion: mark the entry as cancelled and skip it when it reaches the top. Changing a priority is the same: mark the old entry dead and push a new one.

Python Lazy deletion and priority updates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The price of lazy deletion is that dead entries linger and use memory until they surface. Rebuild the heap if too many of them accumulate.

heapq versus queue.PriorityQueue

queue.PriorityQueue wraps a heap in a class with put and get. It adds locks for thread safety, which makes each call slower, and it has no peek or heapify. Use it only when several threads share one queue. For single-threaded work (algorithms, simulations, Dijkstra), heapq is simpler and faster.

Common mistakes

  • Treating the list as sorted. Only heap[0] is the minimum. Do not read heap[1] as the second smallest.
  • Mutating the list directly. heap.append(x), heap[i] = y and heap.sort() can break the heap invariant. Use heappush, heappop, heapreplace, or call heapify again afterward.
  • Forgetting that it is a min-heap. For largest-first, negate values or use the 3.14 _max functions.
  • Mixing min and max functions on one list.
  • Equal priorities with incomparable payloads. Use the counter trick.
  • Peeking an empty heap. heap[0] raises IndexError, so test if heap: first.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. After h = [] and pushing 5, 2, 8 with heappush, which expression is guaranteed to be the smallest value?

    The root of the heap, index 0, is always the minimum. The rest of the list is only partially ordered.
  2. 2. How do you pop the largest number first using only the classic heapq functions?

    heapq is a min-heap and has no reverse option in the classic functions. Negating values turns the largest into the smallest. Python 3.14 also adds heappush_max and heappop_max.
  3. 3. Why does heappush(h, (1, {'a': 1})) followed by heappush(h, (1, {'b': 2})) raise a TypeError?

    Tuples compare element by element. After the equal first elements, Python tries to compare the dicts with <, which is not supported. A unique counter as the second element avoids it.
  4. 4. What is a good use of heapq.nlargest(k, data)?

    nlargest keeps a heap of size k, so it runs in about O(n log k) time with O(k) memory. For k close to n, plain sorted() is simpler.
  5. 5. What is the difference between heappushpop(h, x) and heapreplace(h, x)?

    heappushpop pushes x first, so it can return x itself. heapreplace removes the current minimum first and then adds x, so it returns the old minimum and fails on an empty heap.

Summary

  • heapq is a min-heap that operates in place on a normal list; heap[0] is the minimum.
  • heappush and heappop are O(log n), heapify is O(n), and nlargest / nsmallest run in about O(n log k).
  • heappushpop and heapreplace combine a push and a pop in one sift.
  • For max-heaps, negate numbers (all versions) or use the _max functions of Python 3.14.
  • Use (priority, counter, payload) tuples to avoid comparing payloads and to get FIFO order among equal priorities.
  • Delete or update items lazily by marking old entries dead.
  • Never modify the list outside the heapq functions.

Next: Top-K and Streaming Problems