Heap Sort
In short: heap sort turns the array itself into a heap, using no extra memory. First it builds a max-heap bottom-up, so the biggest value sits at index 0. Then it repeats one move: swap the root with the last unsorted slot, shrink the heap by one, and sift the new root down to fix the one violation that swap created. Each sift-down costs O(log n), and there are n of them, so the whole sort is O(n log n) time and O(1) extra space — but it is not stable: equal keys can come out in a different order than they went in.
Rank a batch of support tickets
Quarry's nightly job ranks a batch of support tickets by priority before anyone reads them, highest first. The tickets already sit in one array — no separate structure needed:
heap_sort builds ascending order, because each extraction moves the current
biggest value to the end. For "highest priority first", read the result
backwards, or flip every comparison to build a min-heap instead.
Watch the heap get built, then watch two extractions shrink it from the right:
Building the heap only fixes parent-child violations, working from the last parent up to the root — most of the array never moves.
Start at the last parent, index 1 (10). Its only child is index 3 (5) — no violation there. 5 cells. At index 1.
Extraction swaps the root into the shrinking heap's last slot, then sifts the new root back down. The sorted suffix on the right only ever grows.
This is already a valid max-heap: 9 beats both of its children, 5 and 7. 5 cells. At index 0.
Why heap sort needs no second array
Merge sort (section 3) is O(n log n) too, but it allocates a new array on
every merge — O(n) extra memory at its peak. Heap sort's whole trick is that
the shape of a complete binary tree has no gaps, so parent, left and
right are just arithmetic on one list. The "heap" and the "array" are the
same object:
heap = [10, 8, 9, 3, 7, 1] # already a valid max-heap
print(heap[0] == max(heap))That is also why the last loop starts at n - 1 and counts down: the sorted
answer is built from the back of the array forward, one confirmed maximum
at a time, while the unsorted front keeps shrinking.
Heap sort scrambles ties
Heap sort compares whatever key you give it, and a sift-down swap does not care whether two items are "equal enough to leave alone". Sort these tickets by priority only, and watch the two priority-2 tickets — and the two priority-5 tickets — change order, with no bug anywhere:
C comes out before A, and D before B — reversed from the order they
arrived in, even though this code has nothing wrong with it. Building the
heap moves items by position in the tree, not by their place in the
original array, so two equal keys can end up on opposite sides of a swap for
reasons that have nothing to do with their value. No comparison-based rule
fixes this without extra bookkeeping (pairing every key with its original
index, which costs memory). If order among equal keys matters, carry the
index alongside the key, or pick a stable sort like merge sort instead.
Quick practice
heap = [50, 40, 45, 10, 30, 20]
print(heap[1] > heap[3], heap[1] > heap[4])def sift_down(heap, i, size):
while True:
left, right = 2 * i + 1, 2 * i + 2
biggest = i
if left < size and heap[left] > heap[biggest]:
biggest = left
if right < size and heap[right] > heap[biggest]:
biggest = right
if biggest == i:
return
heap[i], heap[biggest] = heap[biggest], heap[i]
i = biggest
heap = [1, 12, 9, 4, 8]
sift_down(heap, 0, len(heap))
print(heap)The two lines inside the extraction loop are in the wrong order. Swap them.
🎯 Your turn
Build heap_sort(arr): return a new list with arr's values in ascending
order, using an explicit max-heap (no sorted(), no heapq).
heap_sort([5, 1, 9, 3, 7])→[1, 3, 5, 7, 9]heap_sort([])→[]
Hint: build the max-heap bottom-up from n // 2 - 1 down to 0, then for
end from n - 1 down to 1: swap heap[0] and heap[end], then
sift_down(0, end) so the shrinking heap stays valid.
Press ▶ Run, try the Live App chips, then ✓ Check.