Using Figure 6.4 as a model, illustrate the operation of HEAPSORT on the array A = [5, 13, 2, 25, 7, 17, 20, 8, 4].
Argue the correctness of HEAPSORT using the following loop invariant:
• At the start of each iteration of the for loop of lines 2-5, the subarray A[1...i] is a max-heap containing the i smallest elements of A[1...n], and the subarray A[i + 1...n] contains the n - i largest elements of A[1...n], sorted.
It is very obvious.
What is the running time of heapsort on an array A of length n that is already sorted in increasing order? What about decreasing order?
If the array is in descending order, then we have the worst case, we need
 )
If it is in increasing order, we still need,Because the cost of Max_heapify doesn't change.
Show that the worst-case running time of heapsort is Ω(n lg n).
Same as 6.3.3.
Show that when all elements are distinct, the best-case running time of heapsort is Ω(n lg n).
It is actually a hard problem, see solution
Follow @louis1992 on github to help finish this task.