Heapsort for sorted input
Hi I have been reading about heapsort in CLRS and came to a question which is what is the running time of heapsort when the input array is in increasing order; how about decreasing order.
The next question asks to prove that worst case of heapsort is O(nlogn). The following starred (hard) question asked to prove that best case running time of heapsort is O(nlogn).
Obviously the later questions render the previous trivial, but I assume that the first 2 can be answered in a more straightforward fashion?
Here is whaty I have done so far ...
For the increasing order (i.e. the order opposite to the output order) I am completely stuck and haven't been able to make any progress because as I see it as soon as we build the max heap the structure completely changes and I cant reason about what the final heap will look like.
For the decreasing case I feel like I understand what is going on and will try to describe that below, but its also a long way from a proof. A decreasing array is already a max heap so the array is unchanged by building the max heap. WLOG assume a complete binary tree (else just remove some elements until you get one)
Remove the first n/4 largest elements. 864
The first element will then be lifted to the top and fall back down a distance of log(n) falling to the left each time (the left element is always the largest).
But now the right is larger for each vertex that this last element fell through. So the next vertex will first fall right then fall left the rest of the way. No vertex will fall the same path until this has been rectified. So elements moved to the top of the tree continue to fall the full length of the tree. Rectifying the tree seems like it will take a linear time because it has length logn and it feels like you have to go down a constant fraction of the other routes before it is done. But this is really wordy and sort of garbage.
I apologise if this could be written better but I tried my best to say what I mean.
Note I have read the proof for the general best case but I was looking for something more straightforward due to the extra information.
Thanks 441