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.