Python heap sort
last modified November 18, 2026 Python 3.15
In this article we explain the heap sort algorithm in Python. We implement
it in place with a max heap, trace it, sort with the heapq
module, and use heaps to find the largest or smallest items without sorting
everything.
Heap sort can be seen as an improved selection sort. Selection sort scans the whole unsorted part to find its maximum. Heap sort keeps the unsorted part in a heap, a data structure that delivers the maximum in O(log n) time.
Binary heaps
A binary heap is a complete binary tree stored in a list. The
children of the node at index i are at indexes
2*i + 1 and 2*i + 2; its parent is at
(i - 1) // 2. In a max heap, every node is greater
than or equal to its children, so the largest element is at index 0. A
min heap, used by the heapq module, keeps the
smallest element at the root.
The basic heap operation is sift down: a node that is smaller than one of its children is swapped with the larger child, and this repeats until the node is in a valid place.
Heap sort algorithm
Heap sort works in two phases. First it turns the list into a max heap. Then it repeatedly swaps the root, the largest element, with the last element of the heap, shrinks the heap by one, and sifts the new root down. The sorted part grows from the end of the list.
| Property | Value |
|---|---|
| Time (best, average, worst) | O(n log n) |
| Building the heap | O(n) |
| Extra space | O(1), sorts in place |
| Stable | no |
Heap sort example
The following is an in-place implementation of heap sort.
def sift_down(vals, root, end):
while True:
child = 2 * root + 1
if child >= end:
return
if child + 1 < end and vals[child + 1] > vals[child]:
child += 1
if vals[root] >= vals[child]:
return
vals[root], vals[child] = vals[child], vals[root]
root = child
def heap_sort(vals):
n = len(vals)
for i in range(n // 2 - 1, -1, -1):
sift_down(vals, i, n)
for end in range(n - 1, 0, -1):
vals[0], vals[end] = vals[end], vals[0]
sift_down(vals, 0, end)
nums = [12, 11, 13, 5, 6, 7]
heap_sort(nums)
print(nums)
The sift_down function works on the heap
vals[0:end]. It picks the larger child and swaps it with the
root while the root is smaller. The first loop builds the heap bottom up,
starting from the last node that has a child; leaves are valid heaps
already. The second loop moves the maximum to the end and restores the heap
in the remaining part.
$ python heap_sort.py [5, 6, 7, 11, 12, 13]
Tracing the algorithm
We print the heap after it is built, level by level, and then the list after each extraction.
def sift_down(vals, root, end):
while True:
child = 2 * root + 1
if child >= end:
return
if child + 1 < end and vals[child + 1] > vals[child]:
child += 1
if vals[root] >= vals[child]:
return
vals[root], vals[child] = vals[child], vals[root]
root = child
def show_levels(vals, end):
level, start = 0, 0
while start < end:
size = 2 ** level
print(f' level {level}: {vals[start:min(start + size, end)]}')
start += size
level += 1
vals = [4, 10, 3, 5, 1, 8, 9]
n = len(vals)
for i in range(n // 2 - 1, -1, -1):
sift_down(vals, i, n)
print('max heap:', vals)
show_levels(vals, n)
for end in range(n - 1, 0, -1):
vals[0], vals[end] = vals[end], vals[0]
sift_down(vals, 0, end)
print(f'extract {vals[end]:>2}: heap {vals[:end]} sorted {vals[end:]}')
In the max heap, every element is greater than its two children in the next
level: 10 is greater than 5 and 9,
5 is greater than 4 and 1, and so on.
After each extraction, the largest remaining element is back at the front
of the heap, and the sorted part at the end grows by one.
$ python heap_trace.py max heap: [10, 5, 9, 4, 1, 8, 3] level 0: [10] level 1: [5, 9] level 2: [4, 1, 8, 3] extract 10: heap [9, 5, 8, 4, 1, 3] sorted [10] extract 9: heap [8, 5, 3, 4, 1] sorted [9, 10] extract 8: heap [5, 4, 3, 1] sorted [8, 9, 10] extract 5: heap [4, 1, 3] sorted [5, 8, 9, 10] extract 4: heap [3, 1] sorted [4, 5, 8, 9, 10] extract 3: heap [1] sorted [3, 4, 5, 8, 9, 10]
Sorting with heapq
The heapq module implements a min heap in C. Popping all
elements from it yields them in ascending order.
import heapq
def heap_sort(iterable):
heap = list(iterable)
heapq.heapify(heap)
return [heapq.heappop(heap) for _ in range(len(heap))]
nums = [9, 1, 8, 2, 7, 3, 6, 4, 5]
print(heap_sort(nums))
heap = nums.copy()
heapq.heapify(heap)
print('min heap:', heap)
The heapify function turns a list into a heap in linear time,
and heappop removes and returns the smallest element. The heap
itself is not sorted; it only guarantees that each element is not greater
than its children. This version is not in place: it builds a new result
list.
$ python heapq_sort.py [1, 2, 3, 4, 5, 6, 7, 8, 9] min heap: [1, 2, 3, 4, 7, 8, 6, 9, 5]
Descending order with max-heap functions
Python 3.14 added public max-heap functions to the heapq
module: heapify_max, heappush_max,
heappop_max, heapreplace_max, and
heappushpop_max.
import heapq
def heap_sort_desc(iterable):
heap = list(iterable)
heapq.heapify_max(heap)
return [heapq.heappop_max(heap) for _ in range(len(heap))]
words = ['sky', 'cup', 'forest', 'war', 'atom', 'cloud', 'tea']
print(heap_sort_desc(words))
print(heap_sort_desc([3, 1, 4, 1, 5, 9, 2, 6]))
Popping from a max heap returns the elements from the largest to the smallest. In older versions, the usual trick was to push negated numbers into a min heap, which does not work for strings.
$ python heap_desc.py ['war', 'tea', 'sky', 'forest', 'cup', 'cloud', 'atom'] [9, 6, 5, 4, 3, 2, 1, 1]
Sorting by key
The heapq functions have no key parameter. We use
the decorate-sort-undecorate pattern: we push tuples whose first element is
the key.
import heapq
from dataclasses import dataclass
@dataclass
class Task:
name: str
priority: int
def heap_sort(items, key):
heap = [(key(item), i, item) for i, item in enumerate(items)]
heapq.heapify(heap)
return [heapq.heappop(heap)[2] for _ in range(len(heap))]
tasks = [Task('backup', 2), Task('deploy', 1), Task('report', 3),
Task('alert', 1), Task('cleanup', 2)]
for task in heap_sort(tasks, key=lambda t: t.priority):
print(task)
pairs = [(1, Task('alert', 1)), (1, Task('deploy', 1))]
try:
heapq.heapify(pairs)
except TypeError as e:
print('TypeError:', e)
The tuples contain the key, the original index, and the item. The index has
two purposes. It breaks ties, so tasks with the same priority come out in
their input order. And it prevents the comparison of the items themselves:
without it, two tuples with equal keys compare their second elements, which
fails with a TypeError for objects that do not define
<.
$ python heap_key.py Task(name='deploy', priority=1) Task(name='alert', priority=1) Task(name='backup', priority=2) Task(name='cleanup', priority=2) Task(name='report', priority=3) TypeError: '<' not supported between instances of 'Task' and 'Task'
Heap sort is not stable
The in-place heap sort moves elements over long distances, so it does not preserve the order of equal elements.
def sift_down(vals, root, end, key):
while True:
child = 2 * root + 1
if child >= end:
return
if child + 1 < end and key(vals[child + 1]) > key(vals[child]):
child += 1
if key(vals[root]) >= key(vals[child]):
return
vals[root], vals[child] = vals[child], vals[root]
root = child
def heap_sort(vals, key):
n = len(vals)
for i in range(n // 2 - 1, -1, -1):
sift_down(vals, i, n, key)
for end in range(n - 1, 0, -1):
vals[0], vals[end] = vals[end], vals[0]
sift_down(vals, 0, end, key)
people = [('Anna', 30), ('Boris', 25), ('Clara', 30), ('David', 25),
('Eva', 30)]
heap_sort(people, key=lambda p: p[1])
print(people)
print(sorted([('Anna', 30), ('Boris', 25), ('Clara', 30), ('David', 25),
('Eva', 30)], key=lambda p: p[1]))
We sort people by age with our heap sort and with sorted. The
30-year-olds come out as Clara, Eva, Anna; sorted keeps the
input order Anna, Clara, Eva. The index trick from the previous example
makes a heap-based sort stable at the cost of extra memory.
$ python unstable.py
[('Boris', 25), ('David', 25), ('Clara', 30), ('Eva', 30), ('Anna', 30)]
[('Boris', 25), ('David', 25), ('Anna', 30), ('Clara', 30), ('Eva', 30)]
Top-k selection
Heaps are most useful when we need only a few of the largest or smallest
items. The nlargest and nsmallest functions find
them without sorting the whole collection.
import heapq
import random
rng = random.Random(3)
scores = {f'player{i:03}': rng.randint(0, 10_000) for i in range(1000)}
top = heapq.nlargest(3, scores.items(), key=lambda e: e[1])
low = heapq.nsmallest(3, scores.items(), key=lambda e: e[1])
print('top 3: ', top)
print('bottom 3:', low)
stream = (rng.randint(0, 1_000_000) for _ in range(100_000))
heap = []
for value in stream:
if len(heap) < 5:
heapq.heappush(heap, value)
elif value > heap[0]:
heapq.heapreplace(heap, value)
print('5 largest of the stream:', sorted(heap, reverse=True))
Both functions accept a key. For the stream, we keep a min heap
of the five largest values seen so far. Its root is the smallest of them; a
new value replaces it with heapreplace only if it is greater.
This processes 100,000 values in O(n log k) time and O(k) memory.
$ python top_k.py
top 3: [('player149', 9975), ('player743', 9972), ('player617', 9959)]
bottom 3: [('player860', 27), ('player295', 29), ('player645', 38)]
5 largest of the stream: [999987, 999954, 999954, 999944, 999919]
Benchmark
We compare our heap sort, the heapq version, and
sorted on 100,000 numbers.
import heapq
import random
import timeit
def sift_down(vals, root, end):
while True:
child = 2 * root + 1
if child >= end:
return
if child + 1 < end and vals[child + 1] > vals[child]:
child += 1
if vals[root] >= vals[child]:
return
vals[root], vals[child] = vals[child], vals[root]
root = child
def heap_sort(vals):
n = len(vals)
for i in range(n // 2 - 1, -1, -1):
sift_down(vals, i, n)
for end in range(n - 1, 0, -1):
vals[0], vals[end] = vals[end], vals[0]
sift_down(vals, 0, end)
def heapq_sort(vals):
heapq.heapify(vals)
return [heapq.heappop(vals) for _ in range(len(vals))]
rng = random.Random(5)
data = [rng.randint(0, 1_000_000) for _ in range(100_000)]
tests = [('heap sort', lambda: heap_sort(data.copy())),
('heapq sort', lambda: heapq_sort(data.copy())),
('sorted', lambda: sorted(data))]
for name, func in tests:
t = timeit.timeit(func, number=3) / 3
print(f'{name:<12} {t:.5f} s')
The pure Python heap sort is the slowest; its inner loop makes many
interpreted comparisons and swaps. The heapq version runs the
sifting in C and is several times faster, and sorted is faster
still. The times vary between runs and machines.
$ python benchmark.py heap sort 0.29012 s heapq sort 0.03646 s sorted 0.01473 s
Source
Sorting Techniques – Python documentation
In this article we have implemented heap sort in Python and used the
heapq module for sorting and top-k selection. See also
Python selection sort,
Python merge sort,
Python quick sort, and
Python sorted function.
Author
List all Python tutorials.