Heapsort
Building a max-heap in the array itself, then swapping the root with the last cell and sifting down: an n log n guaranteed sort, in place, unstable, compared with merge sort and quicksort.
- 22 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
A few cards from the deck
Heapsort: what is it?
Show the answer
A sort that first turns the array into a max-heap, then repeatedly removes the largest element by placing it at the end of the array.
The heap lives inside the array itself and the sorted zone grows from the right: no auxiliary memory is needed.
What array results from turning
[3, 9, 2, 7, 5]into a max-heap by successive sift-downs, from the last parent to the root?[9, 7, 2, 3, 5][9, 5, 2, 3, 7][9, 3, 2, 7, 5][3, 9, 7, 2, 5]
Show the answer
[9, 7, 2, 3, 5]The last parent is in cell 1 (9): larger than 7 and 5, it stays. Then the root 3 sinks: swapped with its larger child, 9, then with 7 (the larger of its children 7 and 5). The result is [9, 7, 2, 3, 5].
Heapsort runs in two phases: … a max-heap, then repeatedly … the root.
Show the answer
Heapsort runs in two phases: building a max-heap, then repeatedly extracting the root.
The first phase arranges the whole array in O(n); the second does n extractions of O(log n) each, hence n log n in total.
Heap construction: what is it?
Show the answer
The phase that sifts each parent down to its place, from the last parent up to the root, so the array satisfies the heap property.
For n elements the last parent is at index n/2 − 1 (integer division): the following cells are leaves, already one-element heaps. This phase costs O(n).