ZetCode

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.

PropertyValue
Time (best, average, worst)O(n log n)
Building the heapO(n)
Extra spaceO(1), sorts in place
Stableno

Heap sort example

The following is an in-place implementation of heap sort.

heap_sort.py
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.

heap_trace.py
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.

heapq_sort.py
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.

heap_desc.py
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.

heap_key.py
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.

unstable.py
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.

top_k.py
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.

benchmark.py
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

heapq – Python documentation

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

I am Jan Bodnar, a programmer and technical writer. I have been writing programming tutorials at ZetCode since 2007 and have published eight e-books. See about the author.

List all Python tutorials.