1. One-Liner
Heap Sort turns the array into a max-heap, then repeatedly moves the largest element to the sorted tail and restores the heap.
2. The Problem It Solves
You want O(n log n) worst-case time without O(n) extra memory like merge sort — useful when space is tight and stability is not required.
3. The Core Idea
A binary heap is a complete tree where each parent is ≥ its children (max-heap). The maximum is always at the root; swap it out, shrink the heap, and sift down the new root.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. | Heapify bottom-up: for i from n/2-1 down to 0, sift down |
| 2. | Swap a[0] (max) with a[n-1] |
| 3. | Consider heap size n-1; sift down from root |
| 4. | Repeat until heap size is 1 |
5. Dry Run Example
[3, 1, 2]: max-heap root 3; swap with last → fix heap on [2,1]; final order 1, 2, 3.
6. Key Properties
| Property | Value |
|---|---|
| In-place | Yes |
| Stable | No |
| Cache | Poorer locality than Quick Sort |
7. Where It Is Used
| Company / System | How They Use It |
|---|---|
| Introsort | Fallback when recursion depth suggests worst-case Quick |
| Embedded | Predictable time, O(1) extra |
8. Interview Tips
Know sift down / heapify; parent/child index formulas; Introsort connection.
9. Comparison with Other Algorithms
| Algorithm | Worst | Extra space | Stable |
|---|---|---|---|
| Heap | O(n log n) | O(1) | No |
| Merge | O(n log n) | O(n) | Yes |
| Quick | O(n²) | O(log n) | No |
10. Complexity
| Metric | Value |
|---|---|
| Time (Best) | O(n log n) |
| Time (Average) | O(n log n) |
| Time (Worst) | O(n log n) |
| Space | O(1) |
| Stable? | No |
Implementation Example (PYTHON)
def heap_sort(arr):
def sift(i, n):
while True:
l, r = 2 * i + 1, 2 * i + 2
m = i
if l < n and arr[l] > arr[m]: m = l
if r < n and arr[r] > arr[m]: m = r
if m == i: break
arr[i], arr[m] = arr[m], arr[i]
i = m
n = len(arr)
for i in range(n // 2 - 1, -1, -1): sift(i, n)
for end in range(n - 1, 0, -1):
arr[0], arr[end] = arr[end], arr[0]
sift(0, end)
return arr