Python

Python heapq — heapify, heappush, heappop, and nlargest

Sorting a whole list to reach its smallest item pays for order the job never uses. The heapq module keeps a list in heap order, where the smallest item always sits at index zero and each push and pop restores that shape at a fraction of a full sort. This guide takes heapify first, then push and pop, what heap order does and does not promise, priority tuples for ordered work, nlargest and nsmallest for the top few, merge for sorted inputs, and the empty-heap errors.

Written November 13, 2026 · Tested with Python 3.12.3 · 9 min read

By the end of this guide
  • The main program: heapify, the smallest item, and draining the heap
  • Push and pop: heappush, heappop, heappushpop, and heapreplace
  • Heap order: what the list does and does not promise
  • Priority tuples: ordering work by a number first

Written November 13, 2026

Tested with Python 3.12.3

What this guide is

The heapq module works on a plain list and keeps it in heap order. Heap order is one promise: the smallest item is at index zero, and every parent is no larger than its children. The list itself is not sorted, and the module does not need it to be. That single promise is enough for a set of common jobs: repeatedly taking the smallest remaining item, running work in priority order, keeping track of the largest few values in a long input, and merging inputs that are already sorted. A program that needs the full order of every item sorts the list instead. A program that needs the smallest item again and again, while new items arrive, uses a heap.

The main program: heapify, the smallest item, and draining the heap

The heapify function turns an existing list into a heap in place. Index zero then holds the smallest item, reading it removes nothing, and each heappop call returns the smallest remaining item and restores heap order. Popping until the heap is empty therefore returns the values in sorted order:

Python
import heapq
scores = [42, 7, 19, 73, 7, 31]
heapq.heapify(scores)
print(scores)
print(scores[0])
print(heapq.heappop(scores))
print(scores)
print([heapq.heappop(scores) for _ in range(len(scores))])

The exact output:

Config
[7, 7, 19, 73, 42, 31]
7
7
[7, 31, 19, 73, 42]
[7, 19, 31, 42, 73]

Read the first printed list closely. It starts with 7, the smallest value, but 73 sits before 42 and 31, so the list is not in sorted order. That is heap order working as stated: the promise covers index zero and the parent and child pairs, not the whole sequence. The last line is sorted because each pop took the current smallest item, one after another, until none were left.

Push and pop: heappush, heappop, heappushpop, and heapreplace

Items join a heap with heappush and leave with heappop. Two combined forms cover common cases in one step. heappushpop pushes a new item and then pops the smallest, which can be the new item itself. heapreplace pops the smallest item first and then pushes the new one, so the new item can never be the value returned:

Python
import heapq
heap = []
for value in [15, 3, 9, 3]:
    heapq.heappush(heap, value)
print(heap)
print(heap[0])
print(heapq.heappop(heap))
print(heap)
print(heapq.heappushpop(heap, 5))
print(heap)
print(heapq.heapreplace(heap, 20))
print(heap)

The exact output:

Output
[3, 3, 9, 15]
3
3
[3, 15, 9]
3
[5, 15, 9]
5
[9, 15, 20]

The heappushpop line pushed 5 and returned 3, the smaller item already in the heap. The heapreplace line returned 5 and then placed 20, leaving 9 at index zero. A job that holds a fixed number of best results uses heapreplace in that shape: the smallest held result leaves, the new candidate takes a place, and the heap size never changes during the swap.

Heap order: what the list does and does not promise

A heap list can look almost sorted and still not be sorted, so code must not read it as a sorted list. The test below builds a heap, shows that it differs from its sorted form, and then reads the values in true order two ways that leave the question settled: sorting a copy, and asking nsmallest for every item:

Python
import heapq
values = [9, 1, 8, 2, 7, 3]
heapq.heapify(values)
print(values)
print(values == sorted(values))
print(sorted(values))
print(heapq.nsmallest(len(values), values))

The exact output:

Config
[1, 2, 3, 9, 7, 8]
False
[1, 2, 3, 7, 8, 9]
[1, 2, 3, 7, 8, 9]

The heap list has 9 before 7 and 8, which sorted order would never do. Printing a heap for a person, or writing it to a file in order, needs one of the two last lines, not the raw list. The raw list is a working structure for the module, in the same way that the internal order of a dictionary view is a storage fact, not a result.

Priority tuples: ordering work by a number first

A heap of tuples compares the first item first, so a pair of a priority number and a task name orders work by the number. When two priorities tie, the comparison moves to the next item, and the names order those tasks by their text. That tie rule is visible in the output: both leading tasks carry priority 1, and the call comes before the fix because its name sorts first:

Python
import heapq
tasks = []
heapq.heappush(tasks, (2, "write report"))
heapq.heappush(tasks, (1, "fix outage"))
heapq.heappush(tasks, (3, "clean desk"))
heapq.heappush(tasks, (1, "call customer"))
print(heapq.heappop(tasks))
print(heapq.heappop(tasks))
print(tasks)
print(len(tasks))

The exact output:

Output
(1, 'call customer')
(1, 'fix outage')
[(2, 'write report'), (3, 'clean desk')]
2

Code that cannot let the second item decide a tie adds a counter as the middle item, so the order tasks arrived in settles the tie and the names are never compared. The shape to keep is the leading number: the heap reads priority from position, not from a field name, so the number must sit first in every tuple in the heap.

nlargest and nsmallest: the top few, with a key

Many jobs need only the largest or smallest few values, not a heap that lives on. nlargest and nsmallest take a count and an iterable and return a sorted list of that many items. A key function states which part of each item counts, in the same shape as the key used when sorting:

Python
import heapq
scores = [42, 7, 19, 73, 7, 31, 58]
print(heapq.nlargest(3, scores))
print(heapq.nsmallest(3, scores))
students = [("Ana", 88), ("Ben", 73), ("Cid", 95), ("Dee", 88)]
print(heapq.nlargest(2, students, key=lambda s: s[1]))
print(heapq.nsmallest(2, students, key=lambda s: s[0]))
print(max(scores))
print(heapq.nlargest(1, scores)[0])

The exact output:

Config
[73, 58, 42]
[7, 7, 19]
[('Cid', 95), ('Ana', 88)]
[('Ana', 88), ('Ben', 73)]
73
73

The key lines split by purpose. With the score as the key, the top two students are the 95 and then one of the two 88 scores, in input order between the tied pair. With the name as the key, the smallest two are the first two names in text order. The last two lines state a boundary: for a single largest value, max states the job directly, and the one-item nlargest form returns the same value inside a list.

merge: one sorted stream from sorted inputs

The merge function takes two or more iterables that are each already sorted and returns an iterator over all of their items in order. It does not sort unsorted input. With reverse set, the inputs must each be in descending order, and the merged stream is descending as well:

Python
import heapq
morning = [1, 4, 9]
afternoon = [2, 3, 10]
evening = [5, 6]
print(list(heapq.merge(morning, afternoon, evening)))
print(list(heapq.merge([30, 10], [20], reverse=True)))
names_a = ["ana", "cid"]
names_b = ["ben", "dee"]
print(list(heapq.merge(names_a, names_b)))

The exact output:

Config
[1, 2, 3, 4, 5, 6, 9, 10]
[30, 20, 10]
['ana', 'ben', 'cid', 'dee']

Log files written in time order, per-day lists that are each in order, and sorted runs from an earlier step are the usual inputs. Because merge returns an iterator, a program can read the combined stream one item at a time and never hold a combined list, which matters when each input is long.

Errors, and a job order

Popping from an empty heap raises IndexError, and heapreplace on an empty heap raises the same error. Both cases are worth a guard when the heap is fed by outside work and can drain. Below the two error cases, a small job list runs in priority order from first pop to last:

Python
import heapq
heap = [4, 1, 7]
heapq.heapify(heap)
print(heapq.heappop(heap))
try:
    heapq.heappop([])
except IndexError as e:
    print(type(e).__name__)
try:
    heapq.heapreplace([], 5)
except IndexError as e:
    print(type(e).__name__)
jobs = [(5, "backup"), (1, "alert"), (3, "report")]
heapq.heapify(jobs)
order = [heapq.heappop(jobs)[1] for _ in range(3)]
print(order)

The exact output:

Output
1
IndexError
IndexError
['alert', 'report', 'backup']

The job order reads the second item of each popped tuple, so the printed list is the run order a worker would follow: the alert first, then the report, then the backup. A loop that pops until a heap is empty should test the heap before each pop, or catch IndexError as the stop signal on purpose, rather than letting it surface as an unexplained failure.

Which choice for which job

Job Choice Why
Smallest item, once min States the job directly
Smallest items, repeatedly Heap with heappop Each pop restores heap order
Work in priority order Priority tuples Number sits first, heap reads it
Largest few of many nlargest with a key Returns only the top few, sorted
Smallest few of many nsmallest with a key Returns only the bottom few, sorted
Full order of every item sorted Heap order is not sorted order
Combine sorted inputs merge Streams items in order, no re-sort
Swap smallest for a candidate heapreplace Size stays fixed during the swap

Checklist

  • Call heapify on an existing list before treating it as a heap; build an empty heap with heappush from an empty list.
  • Read the smallest item at index zero; never read a heap list as if it were sorted.
  • Put the priority number first in every tuple in a priority heap, and add a counter when arrival order should settle ties.
  • Use nlargest or nsmallest with a key when only the top few items are needed.
  • Feed merge only inputs that are already sorted, in descending order when reverse is set.
  • Guard pops from a heap that can be empty, or catch IndexError as a deliberate stop.

Sources

  • Python Standard Library, heapq — heapify, heappush, heappop, heappushpop, heapreplace, nlargest, nsmallest, and merge, the heap invariant, and priority-queue use with tuples.
  • Python HOWTO, Sorting — key functions and tuple comparison in ordering, which the nlargest key and the priority-tuple sections rely on.

Keep Exploring