Heapsort

Heapsort uses a binary heap to sort an array in $O(n\log n)$ time. It can sort the array in place, with $O(1)$ auxiliary space.

After reading this chapter, you should be able to:

• Sort an array through a priority queue in $O(n\log n)$, as a faster version of selection sort
• Rearrange an array into a heap in place by sinking each internal node from the bottom up
• Show that the bottom-up build is $O(n)$ by bounding each node’s sink by its height rather than by the height of the tree
• Implement in-place heapsort as a max-heap build followed by a sortdown
• Show that heapsort runs in $O(n\log n)$ time with $O(1)$ auxiliary space
• Compare heapsort with the other sorts by time, space, stability, and cache locality

You can download the accompanying code for this chapter: starter and solution.

Sections

1. Sorting with a Priority Queue
2. Tracing the Priority Queue Sort
3. Building a Heap from an Array
4. Using sink to Build a Heap
5. Tracing the Build
6. Building the Heap in Code
7. Emptying the Heap
8. Two Changes to sink
9. The Complete Sort
10. Tracing the Complete Sort
11. Why the Build Is Linear
12. In-Place and Stable?
13. Heapsort and Cache Locality