Sorting through a heap
Heap sort uses a binary heap, a tree stored implicitly in an array where every parent outranks its children. With a max heap the largest element always sits at the root.
Two phases
- Build the heap: starting from the last parent and moving up, sift down each node so the whole array satisfies the heap rule. Building bottom up is cheaper than inserting one by one.
- Extract repeatedly: swap the root with the last element, shrink the heap by one, and sift the new root down. The largest value settles at the end each time, so the array becomes sorted.
Properties
- It sorts in place, needing only a constant amount of extra space.
- Its worst case time matches its average, with no pathological input like quicksort can have.
- It is not stable: equal elements may swap relative order.
- In practice its scattered memory access often makes it slower than quicksort despite equal asymptotic time.
Where it fits
- Good when you need guaranteed worst case behaviour and minimal extra memory.
- The heap itself doubles as a priority queue for streaming top elements.
Key idea
Heap sort builds a heap then repeatedly extracts the maximum into place, giving in place sorting with a guaranteed worst case but no stability.