Sorting Algorithm
Heap Sort
“The Space Saver”
History
Introduced by J.W.J. Williams in 1964. It was a breakthrough because it offered the speed of Merge Sort () without the memory penalty.
It repurposes the "Heap" data structure—usually used for Priority Queues—to sort a list. It feels like a magic trick: you throw data into a pile, and when you pull it out, it's sorted.
How It Works
Heap Sort turns the array into a Binary Heap (a specific type of tree) where the parent is always larger than the children.
The Algorithm Step-by-Step
- Heapify: Rearrange the array so it satisfies the Max-Heap property. The largest item is now at index 0.
- Swap: Move the item at index 0 to the end of the array (it's now sorted).
- Shrink: Pretend the array is one slot shorter.
- Repair: The new item at index 0 is probably wrong. "Sift" it down until the Heap property is fixed.
- Repeat: Until the heap is empty.
Even on a good day, it has to build the heap and dismantle it.
Like Merge Sort, it is consistent. No nasty surprises.
It is generally slower than Quick Sort due to 'cache thrashing' (jumping around memory indices), but it has better worst-case guarantees.
The killer feature. It sorts in-place. No extra arrays needed.
Code Walkthrough
Real implementations in multiple programming languages. Select a language to view idiomatic code.
1def heap_sort(arr: list[int]) -> None:2 """Sort array in-place using heap sort."""3 n = len(arr)45 # Build max heap6 for i in range(n // 2 - 1, -1, -1):7 heapify(arr, n, i)89 # Extract elements from heap one by one10 for i in range(n - 1, 0, -1):11 arr[0], arr[i] = arr[i], arr[0]12 heapify(arr, i, 0)1314def heapify(arr: list[int], n: int, i: int) -> None:15 """Maintain max-heap property for subtree rooted at index i."""16 largest = i17 left = 2 * i + 118 right = 2 * i + 21920 if left < n and arr[left] > arr[largest]:21 largest = left22 if right < n and arr[right] > arr[largest]:23 largest = right2425 if largest != i:26 arr[i], arr[largest] = arr[largest], arr[i]27 heapify(arr, n, largest)Real World Use Cases
- 1Embedded systems with limited memory
- 2Real-time systems where worst-case latency matters
- 3Security-critical systems (to prevent timing attacks)
- 4Introsort (used as the fallback when Quick Sort goes deep)
Key Insights
- It is NOT stable.
- It sorts in-place.
- It has poor cache locality (jumps around the array).
- It is excellent for 'Top K' elements problems.
When to Use
Use Heap Sort when you need performance but cannot spare the memory for Merge Sort. It's the 'safe' choice for restricted environments.
When NOT to Use
If you want raw speed (Quick Sort is faster) or stability (Merge Sort is stable).
Related Algorithms
Try It Yourself
Watch how this algorithm behaves on different inputs. Click a demo to launch the visualizer.