Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Building a Binary Heap from Scratch to Power Heapsort in Python

Heapsort sits in a peculiar corner of the sorting algorithm zoo. It does not get the celebrity status of quicksort, nor the elegance of mergesort, yet it guarantees an O(n log n) bound in the worst case while sorting in place, which makes it attractive when memory is tight. For a Python developer in Melbourne's bustling tech precinct or a student at the University of Sydney tinkering through an algorithms unit, building a heapsort from first principles is one of those exercises that ties together trees, arrays, and recursion in a satisfying loop.

A binary heap is the data structure that makes this possible. At heart it is a nearly complete tree where every parent dominates (or is dominated by) its children, depending on whether you choose a max-heap or a min-heap. The "nearly complete" property is what allows the whole structure to be packed into a contiguous list without needing pointers, and that compactness is what gives heapsort its in-place reputation.

This article walks through building a binary heap in Python, then uses it to drive a working heapsort routine. The implementation leans on the standard list type, so there is no exotic dependency to wrangle. By the end you should be able to picture the heap as both a tree and an array, sift elements up and down with confidence, and reason about why the algorithm behaves the way it does on inputs of different shapes.

If you are hungry for the broader context of how algorithmic thinking feeds into modern pipelines, the article on machine learning foundations at hello ML provides a complementary read. It is a reminder that the same recursive patterns behind a heap show up again in gradient boosting and decision trees.

The Anatomy of a Binary Heap

A binary heap is a complete binary tree that satisfies the heap property. Complete here means every level is filled from left to right, with the final level possibly incomplete but with all nodes pushed as far left as possible. This shape is what allows a heap of n elements to be stored in a list of length n without any gaps.

In a max-heap, every parent node is greater than or equal to its children. In a min-heap, every parent is less than or equal to its children. Heapsort, as typically implemented, relies on a max-heap so that the largest element can be repeatedly extracted from the root. Once you have that, swapping the root with the last unsorted element and sifting the new root down restores the heap property on a smaller range.

The parent-child indexing convention is worth memorising because it appears in every implementation. For a zero-indexed array, the children of the node at index i are at 2i + 1 and 2i + 2, while the parent of index i sits at (i - 1) // 2. These formulas are the entire arithmetic backbone of a heap, and getting them off by one is the classic bug that wastes a Sunday arvo for everyone learning the topic.

Key properties to remember:

Representing a Heap with a Plain Python List

Python lists are dynamic arrays under the hood, which makes them a natural fit for a heap. You append new elements to the end and read them by index, both in constant amortised time. There is no need for a node class or explicit left and right pointers, because the index arithmetic does the work.

A common starting point is a small wrapper class so the heap is reusable. Something like class BinaryMaxHeap: def __init__(self): self.data = [] is enough scaffolding. From there you add methods for size, push, pop, and a peek at the maximum without removing it. The peek operation, in particular, is trivial: it returns self.data[0] if the heap is non-empty, otherwise raising an exception or returning a sentinel.

The compactness of this representation has a real cost-benefit story to it. A pointer-based heap would allocate a node object for every element, which inflates memory and slows down allocation. Storing the heap inline in a list keeps the data dense, which is friendlier to CPU caches. That is one reason heapsort, despite having a worse constant factor than quicksort, can outperform quicksort on certain large inputs, especially on machines like the Monash HPC cluster where cache behaviour matters.

When you reuse the same list for heapsort, the trick is that the heap shrinks from the right side as sorted elements accumulate. The list does not get cleared or recreated; instead, the boundary between heap and sorted region slides leftward with each iteration. This is the in-place guarantee in action.

The Sift-Down Operation

Sift-down, sometimes called heapify-down or bubble-down, is the operation that restores the heap property after the root has been replaced by a smaller element. It compares the parent with both children, swaps with the larger child if that child is greater, and recurses on the swapped index until the element settles into a valid position.

In Python, a clean implementation looks like this:

def _sift_down(self, start, end):
    root = start
    while True:
        child = 2 * root + 1
        if child >= end:
            break
        if child + 1 < end and self.data[child] < self.data[child + 1]:
            child += 1
        if self.data[root] >= self.data[child]:
            break
        self.data[root], self.data[child] = self.data[child], self.data[root]
        root = child

The start and end parameters are essential because they let sift-down operate on a subarray. During heapsort, the heap region shrinks, so passing the current boundary is what allows the same routine to be reused after every swap. Without that generality, you would need a separate routine for the heap construction phase and the sort phase.

A common bug is to forget the child + 1 < end check before picking the right child, which causes an out-of-bounds read when the heap has an even number of elements. Another is to compare only the left child, which leaves the heap in an invalid state if the right child is the larger of the two. Both bugs produce heaps that sort incorrectly, and the failure mode is silent rather than loud, which makes them particularly nasty to track down over a long debugging session.

Constructing a Heap from an Unsorted Array

There are two ways to turn an arbitrary list into a valid heap. The naive approach appends each element one by one and sifts it up, which takes O(n log n) time. The smarter approach, known as bottom-up heapify, calls sift-down on every internal node starting from the last parent and working back to the root, and it runs in linear time.

The intuition behind the linear bound is that most nodes sit near the leaves, where sift-down has very little work to do. Roughly half the nodes are leaves and do nothing at all, a quarter move at most one level, an eighth move at most two levels, and so on. Summing those geometric series gives O(n), which is a lovely result that surprises many students the first time they see it.

In practice, the bottom-up variant is what every textbook heapsort uses because it dominates the alternative. The implementation is short:

def heapify(self, arr):
    self.data = arr[:]
    n = len(self.data)
    for i in range((n - 2) // 2, -1, -1):
        self._sift_down(i, n)

A useful exercise is to log the array after each iteration. Watching the largest value walk towards index 0 as the loop progresses is one of those small visual payoffs that makes algorithmic work feel less abstract. If you prefer a more numerical way of building intuition, the related numerical-methods article on the Newton-Raphson root-finding method shows a similar pattern of refining an approximation step by step, where each iteration moves the estimate closer to the target.

The Heapsort Algorithm in Action

With a working heap, heapsort itself is almost anticlimactic in its simplicity. You build a max-heap from the input, then repeatedly swap the root with the last element of the heap region, shrink the heap region by one, and sift the new root down. Each swap places the current maximum at its final position in the sorted tail.

The core loop in Python looks like this:

def heapsort(arr):
    heap = BinaryMaxHeap()
    heap.heapify(arr)
    end = len(arr)
    while end > 1:
        end -= 1
        arr[0], arr[end] = arr[end], arr[0]
        heap._sift_down(0, end)
    return arr

Notice that the sort happens in place, so the function returns the same list that was passed in. There is no auxiliary array, which is the defining feature of heapsort. Quicksort is also in place but has a worst case of O(n²); mergesort is stable but needs O(n) extra memory. Heapsort carves out its own niche by offering O(n log n) worst case with O(1) extra space, which is a rare combination.

For an Australian developer shipping code to a production system, the practical question is whether heapsort should ever replace the built-in sorted() or list.sort(). The honest answer is almost never for general use, because Timsort (the algorithm behind those functions) is heavily optimised and tuned for real-world data patterns. Heapsort earns its place in interviews, in teaching, and in embedded environments where predictability and bounded memory matter more than raw speed.

Complexity Analysis and Practical Considerations

Heapsort runs in O(n log n) time for best, average, and worst cases, and uses O(1) auxiliary space beyond the input array. The constant factor, however, is higher than quicksort or mergesort because of the cache-unfriendly pattern of swaps between distant indices. Every swap in the sift-down can move an element across a large swath of the array, which tends to evict cache lines and slow down modern hardware.

A useful comparison to keep in mind:

For Python specifically, the language guarantees that list.sort() and sorted() use Timsort, which is a hybrid of merge sort and insertion sort designed by Tim Peters. That means you get strong performance on partially sorted data, which heapsort cannot match. If you are working on a project for a Brisbane fintech or a Perth mining-data platform and need a custom sort, reaching for heapsort is rarely the right call.

That said, heapsort is far from obsolete. It shows up in operating system schedulers, in graph algorithms like Dijkstra's where a priority queue is needed, and in any system where worst-case guarantees matter. Even if you never ship heapsort in production, building it yourself once is a rite of passage that sharpens your sense of how tree-shaped abstractions map onto flat memory, and that skill pays dividends whenever you are reasoning about caches, indexes, or tree-backed storage.