Skip to content

Volume ITechnology

4.0.29 — Heap Sort ​

Classic · Medium · asked in college exams and by interviewers who want "in place and never O(n^2)"

The problem ​

Sort a list in increasing order, in place, in O(n \log n) time even in the worst case.

[4, 10, 3, 5, 1]  →  [1, 3, 4, 5, 10]

Merge sort is never slow, but needs O(n) extra memory. Quicksort is in place, but can fall to O(n^2). Heap sort gets both good properties at once.

The idea in one sentence ​

Heap sort is selection sort (4.0.25) with a faster way to find the largest remaining value.

Selection sort spends O(n) each round searching for the extreme value. Heap sort first arranges the list into a shape called a max-heap, where the largest value always sits at the front. Taking it out and repairing the heap costs only O(\log n). So n rounds cost O(n \log n).

J. W. J. Williams invented the heap and heap sort in 1964. Robert Floyd improved the first step the same year.

A list that is secretly a tree ​

A binary tree is a set of boxes, called nodes, where each node has up to two children below it, a left child and a right child. The node at the top is the root.

A list can describe a tree with no pointers at all. Put the root at index 0. Then fill the tree level by level, left to right. With that layout, a simple rule finds the family of any node:

  • the left child of index i is at 2*i + 1
  • the right child is at 2*i + 2
  • the parent is at (i - 1) // 2
the list10534101234indexthe same list as a tree105341index 0, rootindexes 1, 2indexes 3, 4children of index 1 are 2·1+1 = 3 and 2·1+2 = 4
One list, two views. The colours match each level of the tree with its stretch of the list. Nothing is stored except the list itself. The tree exists only in the index arithmetic.

Why does 2*i + 1 work? Level 0 holds 1 node, level 1 holds 2, level 2 holds 4, and so on. Each level is twice as big as the one above. When you fill level by level, the children of the node at index i always come right after the children of every node before i. Each of those i earlier nodes has two children, which fill 2*i slots after the root. So i's first child lands at 2*i + 1.

The max-heap rule ​

A max-heap is a tree like this where every parent is at least as big as its children. In the picture, 10 is bigger than 5 and 3, and 5 is bigger than 4 and 1. So that list is a max-heap.

The rule says nothing about left versus right, or about cousins. It is much weaker than being sorted. But it guarantees one useful thing: the largest value is at the root, index 0. Any bigger value would have to be the child of something smaller, which breaks the rule.

The repair step: sift down ​

Suppose the root holds a value that is too small, but both subtrees below it are valid heaps. Sift down fixes it. Compare the node with its two children. If a child is bigger, swap the node with its bigger child. Repeat from the node's new position, until it is bigger than both children or has no children.

Why swap with the bigger child? That child becomes the parent of the other child. It must be at least as big as its sibling, or the rule breaks right there.

The tree is about \log_2 n levels tall, and sift down moves one level per swap. So it costs O(\log n).

The solution ​

python
def sift_down(nums: list[int], i: int, size: int) -> None:
    while True:
        largest = i
        left, right = 2 * i + 1, 2 * i + 2
        if left < size and nums[left] > nums[largest]:      # (1)
            largest = left
        if right < size and nums[right] > nums[largest]:
            largest = right
        if largest == i:                                     # (2)
            return
        nums[i], nums[largest] = nums[largest], nums[i]      # (3)
        i = largest

def heap_sort(nums: list[int]) -> None:
    n = len(nums)
    for i in range(n // 2 - 1, -1, -1):                      # (4)
        sift_down(nums, i, n)
    for end in range(n - 1, 0, -1):                          # (5)
        nums[0], nums[end] = nums[end], nums[0]              # (6)
        sift_down(nums, 0, end)                              # (7)

a = [4, 10, 3, 5, 1]
heap_sort(a)
print(a)   # → [1, 3, 4, 5, 10]

b = [5, 5, 2, 9, 1, 9]
heap_sort(b)
print(b)   # → [1, 2, 5, 5, 9, 9]

(1) A child exists only if its index is inside the heap, below size. Then pick whichever of the node and its children is biggest.

(2) The node is already at least as big as both children. The heap rule holds here, so stop.

(3) Swap with the bigger child and continue from that child's position.

(4) Build the heap. Indexes from n // 2 onward have no children, since 2*i + 1 would be past the end. A single node is already a valid heap. So start from the last node that has a child, and sift down each node, working backwards to the root. When we reach a node, both of its subtrees are already heaps, which is exactly what sift down needs.

(5) Now sort. end is the last position of the shrinking heap.

(6) The largest remaining value is at index 0. Swap it to position end, its final sorted place. The sorted part grows from the right.

(7) The value swapped to the root is probably too small. Sift it down, but only within the heap, which is now nums[0:end]. The sorted values after end are left alone.

Trace ​

On [4, 10, 3, 5, 1].

Building the heap. n = 5, so start at index 5 // 2 - 1 = 1.

  • Index 1 holds 10. Its children are 5 and 1. 10 is bigger, so nothing moves.
  • Index 0 holds 4. Its children are 10 and 3. Swap 4 with 10. Now 4 is at index 1, with children 5 and 1. Swap 4 with 5. The list is [10, 5, 3, 4, 1], the heap in the picture.

Sorting.

endswap root to endafter sift downsorted part
410 ↔ 1: 1 5 3 4 | 105 4 3 1 | 1010
35 ↔ 1: 1 4 3 | 5 104 1 3 | 5 105 10
24 ↔ 3: 3 1 | 4 5 103 1 | 4 5 104 5 10
13 ↔ 1: 1 | 3 4 5 101 | 3 4 5 10all

Complexity, worked out ​

The sorting phase. n - 1 rounds. Each does one swap and one sift down of O(\log n). Total: O(n \log n).

Building the heap is only O(n), not O(n \log n). Here is why. Sift down's cost depends on how far a node is from the bottom, not the top. About half the nodes are leaves, at the bottom, and are never sifted at all. A quarter sit one level up and move at most one level. An eighth move at most two levels. Adding it up:

\frac{n}{4} \times 1 + \frac{n}{8} \times 2 + \frac{n}{16} \times 3 + \dots

This sum stays below n, however many terms you add. The many nodes near the bottom are cheap, and the few expensive nodes near the top are rare. So building is O(n). The whole sort is still O(n \log n), because of the sorting phase.

The worst case is also O(n \log n). No input makes sift down go deeper than the height of the tree.

Memory. Everything happens inside the list, and sift_down uses a loop, not recursion. So it is O(1) extra memory.

CaseTime
BestO(n \log n)
AverageO(n \log n)
WorstO(n \log n)
Extra memoryO(1)
StableNo

Why not use it all the time? ​

On paper, heap sort beats both merge sort and quicksort. In practice, it is usually slower than quicksort, for one reason: it jumps around in memory. Sift down goes from i to 2i + 1, then to about 4i, and so on. Those positions are far apart in a large list. Processors are fast at reading memory that sits close together, and slow at reading scattered positions. Quicksort reads straight along the list.

So heap sort is mainly used as a safety net. C++'s introsort switches to heap sort when quicksort's recursion goes too deep. That keeps quicksort's speed, but guarantees O(n \log n).

It is not stable either. The swap of the root to the end jumps elements over equal ones.

The heap is more useful than heap sort ​

The heap itself is one of the most important structures in programming. It is the standard way to build a priority queue: a queue where you always take out the most urgent item, like a hospital emergency room. Python provides one in the heapq module. It is a min-heap, with the smallest value at index 0, but the index rules are the same.

python
import heapq

nums = [4, 10, 3, 5, 1]
heapq.heapify(nums)                                  # O(n) build, as above
print([heapq.heappop(nums) for _ in range(len(nums))])   # → [1, 3, 4, 5, 10]

Chapter 4.16 teaches heaps in full. Chapter 4.17 then uses them for "top k", "merge k sorted lists" and "running median".

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"Where are the children of index i?" At 2*i + 1 and 2*i + 2. The parent is at (i - 1) // 2.

"Why does building the heap take only O(n)?" Most nodes are near the bottom of the tree, and they move only a short way or not at all. Only a few nodes near the top move far. When you add it all up, the total stays below n.

"Why does the build loop start at n // 2 - 1?" Every index after that has no children. A node with no children already follows the heap rule.

"Heap sort is always O(n \log n) and needs no extra list. Why isn't it the default?" It jumps around in memory, which is slow on real computers. Quicksort is usually faster in practice. Heap sort is also not stable.

One thing to volunteer: "Heap sort is selection sort with a heap. The heap finds the biggest value without searching the whole list."

Next: 4.0.30 Counting Sort and Radix Sort. Two sorts that beat O(n \log n), by never comparing two elements at all.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet