Week 79 of 125
TAOCP 5.2.3 Sorting by Selection
Sign up or sign in to tick these off and give this week a due date.
-
Straight selection, tree selection (tournaments), and heapsort with the heap data structure, plus analysis and the use of heaps as priority queues.
Time About 8 hours this week
Why it matters
Heaps are the standard priority queue, used in Dijkstra, schedulers and top-k queries. Heapsort is the in-place O(n log n) worst-case fallback in introsort.
Before you start
- 5.2.2 Sorting by Exchanging
- 2.3 Trees
How to approach it
Implement heapsort from scratch with an array-based heap. Then implement a priority queue with insert and delete-min and use it for something real like merging k sorted files.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Off-by-one in parent and child index formulas, especially 0-based versus Knuth's 1-based arrays.