[Algo] Exercise 6.4

Exercise 6.4-3
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?
increasing order: Even though it is in increasing order, it must be trasnformed into a max-heap. And each time we call MAX-HEAPIFY it must traverse from the root to leaves, so it takes $O(n\lg n)$ time to run heapsort.
decreasing order: Though it takes less time to run BUILD-MAX-HEAP, but it still takes $O(\lg n)$ time to call MAX-HEAPIFY. Thus it takes $O(n \lg n)$ time to run heapsort.


Exercise 6.4-4
Show that the worst-case running time of heapsort is $\Omega(n \lg n)$.
HEAPSORT 的 worst-case 發生在第 5 行反覆 call MAX-HEAPIFY 的時候 MAX-HEAPIFY都是 worst-case，根據 Exercise 6.2-6，MAX-HEAPIFY 的 worst-case running time 是 $\Omega(\lg n)$，所以 HEAPSORT 的 worst-case running time is $\Omega(n \lg n)$。


Exercise 6.4-5
Show that when all elements are distinct, the best-case running timeof heapsort is $\Omega(n \lg n)$.