# 8.4 Heap Sort

> Build a max-heap in the array, then repeatedly swap the root (the largest item) to the end and sift down. O(n log n) in every case, in-place.

Chapter: Advanced Sorting & Searching · ~55 min · hard
URL: https://dsa.fetehadin.com/learn/heap-sort

## Mental model

A **sports knockout tournament**. The champion ends up at the top. Remove the champion and the runners-up compete again; the next winner rises to the top. Heap sort keeps finding "the champion" (the maximum) and moving it to the end.

### What is a max-heap?

A **complete binary tree** where every parent is **≥ its children**. So the largest item is always at the **root**.

Because the tree is complete, it fits in an array with no gaps (0-based):

| | index |
| --- | --- |
| left child of i | 2i + 1 |
| right child of i | 2i + 2 |
| parent of i | (i − 1) / 2 |

### heapify (sift down)

If a node is smaller than a child, swap it with the **larger** child and keep going down. O(log n).

### Heap sort in two phases

1. **Build** a max-heap: call heapify on every non-leaf, from `n/2 − 1` down to 0.
2. **Extract** repeatedly: swap `a[0]` (the max) with the last item of the heap, shrink the heap by 1, and heapify the root.

The sorted part grows from the right, just like selection sort, but each "find the max" costs **O(log n)** instead of O(n).

> The same heap is a **priority queue** (`std::priority_queue`), used in Dijkstra's algorithm and schedulers.

## C++ code: heap-sort.cpp

```cpp
#include <iostream>
using namespace std;

void heapify(int a[], int n, int i) {         // sift a[i] down in a max-heap of size n
    int largest = i;
    int l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && a[l] > a[largest]) largest = l;
    if (r < n && a[r] > a[largest]) largest = r;
    if (largest != i) {
        swap(a[i], a[largest]);
        heapify(a, n, largest);
    }
}

void print(int a[], int n) { for (int k = 0; k < n; k++) cout << a[k] << " "; cout << "\n"; }

void heapSort(int a[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)      // build the max-heap
        heapify(a, n, i);
    cout << "max-heap: "; print(a, n);
    for (int end = n - 1; end > 0; end--) {
        swap(a[0], a[end]);                   // biggest goes to the end
        heapify(a, end, 0);
    }
}

int main() {
    int a[] = {4, 10, 3, 5, 1, 8};
    int n = sizeof(a) / sizeof(a[0]);
    heapSort(a, n);
    cout << "sorted:   "; print(a, n);
}
```

Expected output:

```text
max-heap: 10 5 8 4 1 3 
sorted:   1 3 4 5 8 10
```

## Complexity

| Case | Cost |
| --- | --- |
| Build heap | O(n) |
| Each extract-max (swap + heapify) | O(log n) |
| Best / average / worst | O(n log n) |

Space: O(1) iterative, O(log n) with recursive heapify
Stable: no
In-place: yes

Heap sort combines merge sort's guaranteed O(n log n) with quick sort's in-place storage, but it is usually slower in practice.

## Videos

- [Heap, Heap Sort, Heapify, Priority Queues](https://youtu.be/HqPJF2L5h9U) (Abdul Bari): Abdul Bari covers heaps, insert, delete, heapify and heap sort in one sitting.
- [Heap sort in 4 minutes](https://youtu.be/2DmK_H7IdTo) (Michael Sambol): A 4-minute visual of the swap-and-heapify loop.

## Exam lens

Likely questions:

- What is a max-heap? Why is it stored in an array?
- For index i, give the indices of its parent, left child and right child (0-based).
- Build a max-heap from `4, 10, 3, 5, 1, 8`. Show the array.
- Trace two steps of heap sort after the heap is built.

Common mistakes:

- Using 1-based formulas (2i, 2i+1) with a 0-based array. With 0-based it is 2i+1 and 2i+2.
- Starting the build loop at i = 0 instead of n/2 − 1, going down to 0.
- Calling heapify on the whole array instead of the shrinking heap size `end`.
- Confusing a heap with a BST. In a heap, left and right children have no order between them.

## Quick check

1. In a 0-based array heap, the children of index 2 are…
   A. 3 and 4
   B. 4 and 5
   C. 5 and 6
   D. 2 and 3
   Answer: C. 2·2 + 1 = 5 and 2·2 + 2 = 6.

2. In a max-heap, the largest item is…
   A. the last item
   B. the root, a[0]
   C. a leaf
   D. anywhere
   Answer: B. Every parent is ≥ its children, so the max sits at the top.

3. Build a max-heap from `4, 10, 3, 5, 1, 8`. Result?
   A. `10 5 8 4 1 3`
   B. `10 8 5 4 3 1`
   C. `1 3 4 5 8 10`
   D. `10 4 8 5 1 3`
   Answer: A. heapify(2): 8 up. heapify(1): 10 stays. heapify(0): 4 swaps with 10, then with 5.

4. Why can a heap be stored in an array with no pointers?
   A. It is sorted
   B. It is a complete binary tree, so there are no gaps
   C. It is a BST
   D. It has no children
   Answer: B. Complete trees fill levels left to right, so index arithmetic finds parents and children.

## Practice

**Trace by hand.** Heap sort `4, 10, 3, 5, 1, 8`. Write the max-heap, then the array after each of the first three swap-and-heapify steps.

Solution:

- max-heap: `10 5 8 4 1 3`
- swap 10↔3, heapify size 5 → `8 5 3 4 1 | 10`
- swap 8↔1, heapify size 4 → `5 4 3 1 | 8 10`
- swap 5↔1, heapify size 3 → `4 1 3 | 5 8 10`


**Implement it.** Write a min-heap priority queue with `push`, `pop` and `top` using a `vector<int>` (sift up on push, sift down on pop).

Hint: Sift up: while `i > 0 && a[(i-1)/2] > a[i]`, swap with the parent and move up.

**Problems:**

- [Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/) (medium). Hint: Keep a min-heap of size k (`priority_queue<int, vector<int>, greater<int>>`). Its top is the answer.
- [Last Stone Weight](https://leetcode.com/problems/last-stone-weight/) (easy). Hint: A max-heap (`priority_queue<int>`). Pop two, push the difference.

## Mastery checklist

- [ ] I can explain a max-heap and its array storage.
- [ ] I can build a heap by hand with heapify.
- [ ] I can trace heap sort's swap-and-heapify loop.
- [ ] I know heap sort is O(n log n), in-place and not stable.