Heap Sort
DSA · Heaps
Theory
Heap sort first builds a max-heap from the array, so the largest element sits at index 0. It then repeatedly swaps the root with the last unsorted element, shrinks the heap by one and sifts the new root down. After n-1 rounds the array is sorted in place. It always takes O(n log n) time and O(1) extra space, but it is not stable.
Why we use it
It guarantees O(n log n) with constant extra memory, unlike merge sort which needs O(n) memory.
When to use it
Use it when memory is tight and worst-case guarantees matter; in practice library sorts are usually faster.
How it works
- Build a max-heap from the array
- Swap root (max) with the last element
- Reduce heap size by 1
- Sift down the new root
- Heap size > 1? Yes: Repeat. No: Array is sorted.
- O(n log n), in place
Syntax
build max-heap (sift down from n//2 - 1 to 0)
for end from n-1 down to 1:
swap arr[0], arr[end]
sift_down(arr, 0, end)
Time: O(n log n) Space: O(1) Not stableExample
def sift_down(a, i, size):
while True:
l, r, big = 2 * i + 1, 2 * i + 2, i
if l < size and a[l] > a[big]: big = l
if r < size and a[r] > a[big]: big = r
if big == i: return
a[i], a[big] = a[big], a[i]
i = big
def heap_sort(a):
n = len(a)
for i in range(n // 2 - 1, -1, -1):
sift_down(a, i, n)
for end in range(n - 1, 0, -1):
a[0], a[end] = a[end], a[0]
sift_down(a, 0, end)
return a
print(heap_sort([12, 11, 13, 5, 6, 7]))Key points
- Build a max-heap, then extract repeatedly
- O(n log n) always
- In place with O(1) extra space
- Not stable