4
$\begingroup$

What is the running time of heapsort when the input array is in increasing order? How about decreasing order? (I came across these questions in CLRS.)


Here is what 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. 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

$\endgroup$
  • 1
    $\begingroup$ I deleted the follow-up questions from your post: two questions is quite enough for one post. If you want to re-ask them, put them in separate questions. (But you might want to wait for an answer to this one, first, as that may help you solve the others on your own.) $\endgroup$ – David Richerby Jan 1 '15 at 11:03
  • $\begingroup$ Do you want $O$-classes or more precise results? $\endgroup$ – Raphael Jan 2 '15 at 5:37
  • $\begingroup$ I was just hoping for big-O. I understand that this will be nlogn because heapsort is nlogn for all inputs. The thing I want to know is does the fact that we have this additional information allow us to solve the problem more simply, the layout of the book suggests that we can, but I'm not sure. Thank you :) $\endgroup$ – Dan Allford Jan 2 '15 at 11:15
2
$\begingroup$

Time complexity of heapsort is $O(n \log n)$ for all types of input. If we have all input we need $O(n)$ time to build the max-heap. Then for sorting the the data, we need to remove the first element of the array then heapify the remaining data and repeat it for $n$ times. Which the act of heapifying for all steps needs $O(n \log n)$ time.

$\endgroup$
  • $\begingroup$ Thank you for your answer. I know the general result that best & worst case is nlogn. I was wondering if there was any way to give a simpler proof in these specific cases. In the book there is this question, followed by a question asking for the best case analysis, so I assumed that there should be a more straight forward way of solving the first problem? $\endgroup$ – Dan Allford Jan 2 '15 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.