How does heap sort work?

Question

Accepted Answer

**Heap sort** builds a **binary heap** from the array, then repeatedly extracts the maximum to produce sorted order. It runs in **O(n log n)** and is **in-place**.

## The idea

A max-heap keeps the largest element at the root. Build the heap (O(n)), then swap the root to the end, shrink the heap, and re-heapify (sift down) — n times.

## Example

```python
import heapq

def heap_sort(arr):
    heapq.heapify(arr)               # min-heap in O(n)
    return [heapq.heappop(arr)       # pop smallest n times
            for _ in range(len(arr))]

heap_sort([5, 2, 8, 1, 3])           # -> [1, 2, 3, 5, 8]
```

A classic implementation does it in place by sifting down within the array.

## Complexity

- **Time:** O(n log n) in all cases. **Space:** O(1) in-place.

## When to use / pitfalls

Use when you need **guaranteed O(n log n)** *and* **O(1) extra memory** (merge sort needs O(n); quicksort risks O(n²)). It is **not stable** and has poor cache locality, so it is often slower in practice than quicksort. The same heap powers **priority queues** and finding the top-k elements.

## Why it matters

Heap sort is the only common sort that is both worst-case O(n log n) and in-place, making it valuable in memory-constrained or guaranteed-bound settings.

The heap structure underneath is broadly useful — priority queues, Dijkstra's algorithm, and streaming top-k.

It cements the idea that the right data structure makes an algorithm efficient.