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 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
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.
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.
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).
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 = largestdef 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.
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.
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:
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.
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 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 heapqnums = [4, 10, 3, 5, 1]heapq.heapify(nums) # O(n) build, as aboveprint([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".
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."