What it costs
- Best case
- O(n log n)No input helps it. Even a sorted array has to be heapified and then dismantled one value at a time.
- Average
- O(n log n)Building the heap is O(n); the n extractions are O(log n) each, and that second phase dominates.
- Worst case
- O(n log n)Guaranteed, like merge sort — but unlike merge sort it needs no extra memory. That combination is unique among the sorts here.
- Extra memory
- O(1)The heap lives inside the array being sorted. No scratch buffers, no recursion — the sift loop is iterative.
- Stable
- NoThe root swap throws values across the whole array, so equal elements are reordered freely.
- Used in practice
- As a backstopSlower than quick sort in reality because it jumps all over memory and defeats the cache. Introsort starts with quick sort and switches to heap sort if the recursion gets too deep — the guarantee without the usual cost.
The tree is not a separate structure — it is the array read differently. The children of a[i] are a[2i+1] and a[2i+2]; its parent is a[(i−1)/2]. So a[0]'s children are a[1] and a[2], and everything from a[n/2] onwards is a leaf with no children at all — which is why the build phase starts halfway along.