Lesson 112
Heap Sort
Build a Max Heap, then Sort Down
1:00How heap sort uses a max-heap to guarantee O(n log n) in-place sorting in every case, and where to prefer it over quicksort or merge sort.
By the end, you can
- State the max-heap invariant and identify which array index holds the maximum.
- Compute the left child, right child, and parent of any node using the index formulas.
- Trace siftDown for a given node, choosing the correct child to swap with.
- Trace Phase 1 (build heap) and Phase 2 (sort down) step by step on a small array.
- Explain why Phase 1 is O(n) and Phase 2 is O(n log n), and why the worst case equals the average case.
- Compare heap sort with quicksort and merge sort on stability, space, and cache performance.
- Identify use cases where a heap or priority queue is the preferred tool.
Up next in Searching & Sorting
