ZERO / HERO
Building the pile bottom-up

Heapify & Heapsort

The analogy

You could build a heap by adding patients one at a time, sifting each into place. Or you could start with everyone in the room and fix the small groups first, then the bigger groups. Fixing from the bottom up turns out to be dramatically cheaper — and it is not obvious why.

Visualizer

Bottom-up build, then sort

step 1 / 26
5
3
8
1
9
2
7
4

Eight values. We will build a heap bottom-up, then sort with it.

import heapq

a = [5, 3, 8, 1, 9, 2, 7, 4]
heapq.heapify(a)      # O(n) bottom-up, in place

# heapsort
def heapsort(a):
    heapq.heapify(a)                       # O(n)
    return [heapq.heappop(a) for _ in range(len(a))]

# why bottom-up is O(n):
# n/2 nodes sift 0 levels, n/4 sift 1, n/8 sift 2 ...
# sum(k * n / 2**(k+1)) -> n
Check yourself

Cost of building a heap bottom-up from n items?