Write HeapSortSteps, which sorts an array inside the array itself, in two phases:
- Build a max-heap: call
siftDownon every parent, from the last one (n / 2 − 1) back to the root. - Sort: repeat — swap the root (the largest) with the last element of the heap, shrink the heap by one, and
siftDownthe new root.
Count the comparisons between elements. Read n and the values; print the array after phase 1, after each of the first three extractions, and at the end. For the input
9
4 10 3 5 1 8 7 2 9
the program prints
Max-heap: [10, 9, 8, 5, 1, 3, 7, 2, 4] after 12 comparisons
After moving 1 to the end: [9, 5, 8, 4, 1, 3, 7, 2, 10]
After moving 2 to the end: [8, 5, 7, 4, 1, 3, 2, 9, 10]
After moving 3 to the end: [7, 5, 3, 4, 1, 2, 8, 9, 10]
Sorted: [1, 2, 3, 4, 5, 7, 8, 9, 10]
Comparisons in total: 34