Heap Sort
Sorting: lesson 9 of 10
Build a heap, then peel the maximum off n times.
Lesson 9 of 10 · 6 min
Heap Sort
Step 1 of 15
Read the array as a binary heap: index i has children 2i+1 and 2i+2.
The Idea
Read the array as a binary heap: index i has children 2i+1 and 2i+2. Sift every non-leaf down and the largest value ends up at index 0. Swap it with the last slot — that value is now final — shrink the heap by one and sift the new root down. Repeat and the array sorts itself, O(n log n) in the worst case, with no second array anywhere.
Real-World Example
A tournament bracket being replayed. The champion is known, collects the trophy and leaves; only the matches along the path they walked need replaying to find who is best of the rest. Nobody re-plays the whole draw.
The Code
def sift_down(a, i, size):
while 2 * i + 1 < size:
big = 2 * i + 1
if big + 1 < size and a[big + 1] > a[big]:
big += 1 # take the larger child
if a[i] >= a[big]:
break
a[i], a[big] = a[big], a[i]
i = big
def heap_sort(a):
for i in range(len(a) // 2 - 1, -1, -1): # build the max-heap
sift_down(a, i, len(a))
for end in range(len(a) - 1, 0, -1): # peel the max off the top
a[0], a[end] = a[end], a[0]
sift_down(a, 0, end)
return a
print(heap_sort([4, 10, 3, 5, 1])) # [1, 3, 4, 5, 10]Your turn
Put the steps in the right order.
- Sift the new root down until the heap rule holds again
- Sift every non-leaf down, from the last one backwards
- Shrink the heap so the swapped-out value is never touched again
- Swap the root with the last value still in the heap
Mini quiz
1 / 3