Foundation · Module 4 · Lesson 6
Heap Sort
Build a heap and repeatedly extract the extreme.
15–25 min readLesson 24 of 123
Lesson 24 of 123
1d streakTheory lesson · Step-by-step
Understand Heap Sort
Build a heap and repeatedly extract the extreme.
Worked approach
Trace the reasoning step by step
- 1Build a max heap in place.
- 2Swap the root with the final active position.
- 3Shrink the heap boundary.
- 4Sift the new root down and repeat.
Concrete example
Sort [3, 1, 4, 2] with a max heap.
- 1Build max heap with root 4.
- 2Swap 4 to the end and repair.
- 3Repeat for 3 and 2.
Repeated extraction creates the sorted suffix [1,2,3,4].
What must remain true (Loop Invariant)
The heap root is the largest remaining value; the suffix after end is already final.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Sort
O(n log n)
O(1)
Include stability and input shape when comparing sorts.When to use it
- Creating order before searching, grouping, deduplicating, or scanning.
- Selecting records using stability, memory, and input-shape constraints.
- Turning pairwise decisions into monotonic scans.
Common mistakes
- Comparing time alone while ignoring stability and auxiliary memory.
- Breaking duplicate order when stability is required.
- Quoting average performance without worst-case behavior.
Practice prompts
- Reproduce the worked Heap Sort example without looking at the trace.
- Change one input condition and explain whether the Heap Sort invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.