heapq — heap queue algorithm

heapq as a min-heap on a list: heapify, heappush, heappop, nsmallest, merge, comparison errors, and a counter for equal priorities. Python 3.13 has no heapq max API.

模块页正文目前为英文。

The heapq module implements a min-heap as a regular Python list. Official documentation states that heap[0] is always the smallest item, that heappop returns the smallest item, and that the algorithms use 0-based indexing. There is no separate heap type: you pass a list to heapify, heappush, and heappop.

These APIs were checked on Python 3.13.12. This page does not document heapify_max, heappush_max, or heappop_max; those functions are not in the 3.13 standard library. If you need a max-heap on 3.13, official guidance is to invert the comparison, for example by storing negated numbers or a wrapper, not to call a 3.14 API.

Examples were checked against Python 3.13. See the official documentation for the complete API.

Python reference overview →

heapify, push, pop, and nsmallest

heapify rearranges a list in place into a heap in linear time. heappush inserts one item and restores the invariant. heappop removes and returns the smallest item. nsmallest and nlargest return lists from any iterable; official documentation notes that for a single extreme value, min() or max() is enough, and for a large n, sorted() may be better. merge lazily merges already-sorted inputs.

heapq.heapify, heapq.heappush, heapq.heappop, heapq.nsmallest, heapq.nlargest, heapq.merge

heapq.heapify(heap)
heapq.heappush(heap, item)
heapq.heappop(heap)
heapq.nsmallest(n, iterable, key=None)
heapq.nlargest(n, iterable, key=None)
heapq.merge(*iterables, key=None, reverse=False)

Turn a list into a min-heap, push and pop the smallest item, or take the n smallest or largest values from an iterable.

ParameterDescription
heapA list that already is, or will become, a heap. heapify mutates it in place.
item / n / iterableheappush inserts item. nsmallest and nlargest take a count and any iterable. merge takes pre-sorted iterables.

Returns: heapify, heappush, and heappop operate on the list; heappop returns the smallest item. nsmallest and nlargest return lists. merge returns an iterator.

  • The heap lists below are the exact shapes measured on Python 3.13.12 after heapify, heappush(0), and heappop. Other valid heap layouts are possible in general; these are the results of this implementation for these inputs.
  • Print the list after heappush in a separate statement from heappop. Passing the same list to print along with heappop can show the post-pop list for both arguments.
python
import heapq

heap = [5, 1, 4, 2]
heapq.heapify(heap)
print(heap, heap[0])
heapq.heappush(heap, 0)
print(heap)
print(heapq.heappop(heap))
print(heap)
print(heapq.nsmallest(3, [5, 1, 4, 2, 8]), heapq.nlargest(2, [5, 1, 4, 2, 8]))
print(list(heapq.merge([1, 4], [2, 3, 8])))

Expected output

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

Official documentation →

Comparison errors and equal priorities

Heap operations compare items with the ordinary < operator. heapify([1, "a"]) raises TypeError because int and str cannot be compared. When two items have the same priority, the remaining fields of a tuple are compared, so (1, "a") comes before (1, "b") by the string, not by insertion order. Official documentation's priority-queue recipe inserts a monotonically increasing counter: (priority, count, value). Equal priorities then keep the insertion order because the counters differ.

heapq.heapify, heapq.heappush, heapq.heappop

heapq.heapify(heap)
heapq.heappush(heap, item)
heapq.heappop(heap)

Incomparable items raise TypeError. Use a counter as a tie-breaker when equal priorities must keep insertion order.

ParameterDescription
itemAny comparable value. A tuple such as (priority, count, value) is the usual way to make equal priorities stable by insertion order.

Returns: heappop returns the smallest item under that comparison.

Raises

  • TypeError — Raised when two items in the heap cannot be compared, as with 1 and "a" on Python 3.13.12.
  • Without a counter, (1, "a") is less than (1, "b") because "a" < "b". That is comparison of the payload, not stability of the original sequence.
python
import heapq

try:
    heapq.heapify([1, "a"])
except TypeError as err:
    print(type(err).__name__)

queue = []
for count, (priority, name) in enumerate([(1, "b"), (1, "a"), (0, "c")]):
    heapq.heappush(queue, (priority, count, name))
print([heapq.heappop(queue) for _ in range(3)])

Expected output

TypeError
[(0, 2, 'c'), (1, 0, 'b'), (1, 1, 'a')]

Official documentation →