Skip to content
Tutorials Center
My learning

Topics

Python Reference ยท Standard Library: Data Structures and Functional Tools

The heapq module

Reference for Python's heapq module: heappush, heappop, heapify, nlargest, nsmallest, merge, priority-queue patterns, tuples as entries and max-heap tricks.

heapq implements a binary min-heap on top of an ordinary list. The smallest item is always at index 0, and pushing or popping takes logarithmic time. That makes it the standard way to build a priority queue or to find the top few items without sorting everything.

The module offers functions, not a class: you keep the list yourself and pass it to each call.

Python
import heapq

h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
print(heapq.heappop(h))  # 1

Try it

Python A priority queue

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.

Python Top-N, merge and max-heaps

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.

Syntax

Python
heapq.heappush(heap, item)
heapq.heappop(heap)
heapq.heapify(x)
heapq.nlargest(n, iterable, key=None)
Function Description
heappush(heap, item) Adds an item, keeping the heap invariant.
heappop(heap) Removes and returns the smallest item.
heappushpop(heap, item) Pushes item, then pops and returns the smallest (faster than doing both).
heapreplace(heap, item) Pops the smallest, then pushes item. The returned value may be larger than item.
heapify(x) Rearranges a list into a heap in place, in linear time.
nlargest(n, it, key=None), nsmallest(n, it, key=None) Lists of the n largest or smallest items.
merge(*its, key=None, reverse=False) Lazily merges already sorted inputs.

Return value: the popped item for the pop functions; None for heappush and heapify; lists for nlargest/nsmallest; an iterator for merge.

Raises: IndexError when popping from an empty heap; TypeError when items cannot be compared.

Usage notes

  • Only index 0 is guaranteed smallest. The rest of the list is a heap, not sorted; heap[1] is not the second smallest. Pop repeatedly, or use sorted(heap), for ordered output.
  • There is no max-heap. Push negated numbers, or wrap items in a class that reverses __lt__. (Private _heapify_max helpers exist but are undocumented.)
  • Tuples compare element by element, so equal priorities fall through to the payload, which may not be comparable. Insert a unique counter as a tiebreaker as shown above, or use a dataclass with order=True and field(compare=False) for the payload.
  • Do not edit a heap list directly. Assigning to elements or sorting with a different key breaks the invariant. A sorted list is already a valid heap, though.
  • Use nlargest/nsmallest for small n, min()/max() for n = 1, and sorted(...)[:n] when n is close to the input size.
  • Updating priorities is not supported; push a new entry and ignore stale ones when popped, or use a dict of entries marked as removed.
  • Not thread-aware. For a blocking, thread-safe priority queue use queue.PriorityQueue, which uses heapq inside.