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.
import heapq h = [] heapq.heappush(h, 5) heapq.heappush(h, 1) print(heapq.heappop(h)) # 1
Try it
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.
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
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 usesorted(heap), for ordered output. - There is no max-heap. Push negated numbers, or wrap items in a class that reverses
__lt__. (Private_heapify_maxhelpers 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=Trueandfield(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/nsmallestfor smalln,min()/max()forn = 1, andsorted(...)[:n]whennis 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 usesheapqinside.
Related
bisect,collections.deque,queuesorted(),min()- Lessons: Data structures, Algorithms