1
$\begingroup$

I'm trying to prove the running time of heapsort on an array sorted in decreasing/increasing order is $\Theta(n\lg n)$ in order to show that the worst-case running time of heapsort is $\Omega(n\lg n)$

The site here https://courses.csail.mit.edu/6.046/fall01/handouts/ps2sol.pdf mentions :

The running time of HEAPSORT on an array A of length n that is sorted in decreasing order will be $\Theta(n\lg n)$. This occurs because even though the heap will be built in linear time, every time the max element is removed and the HEAPIFY is called it will cover the full height of the tree.

It's the last line which I can't understand. I tried the array A <7, 6, 5, 4, 3, 2, 1>. The first time MAX-HEAPIFY is called, the full height of the tree is covered and I get <6, 4, 5, 1, 3, 2> 7. However, the second time itself the full height of the tree is not covered and I get <5, 4, 2, 1, 3> 6, 7. How does that statement hold then?

Also I see people writing on similar lines saying each call to MAX-HEAPIFY performs full $\lfloor \lg k \rfloor$ operations, where k (I'm assuming) is the number of nodes in the modified heap in each iteration, thereby obtaining the summation. $$ \sum_{i=1}^{n-1}\lg{(n-i)}= \lg\Big((n-1)!\Big) = \Theta(n\lg{n}) $$

Can someone help me realize this. I just want to understand how MAX-HEAPIFY covers the full height of the tree each time it is called.

UPDATE: I'm trying to obtain a proof for the running time to be $\Theta(\lg n)$. During HEAPSORT, if each node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree, that would mean that each call to MAX-HEAPIFY won't perform full $\lfloor \lg k \rfloor$ operations but $ \Theta(\lg k) $ operations, right? (I know $\lfloor \lg k \rfloor $is also $\Theta(\lg k)$ but all I need is for MAX-HEAPIFY to perform $\Theta(\lg k) $ operations each time) $$ \sum_{i=1}^{n-1}\Theta( \lg{(n-i))} = \Theta\Big(\lg\Big((n-1)!\Big)\Big) = \Theta(n\lg{n}) $$ But that statement doesn't hold as pointed out in the comments. Now I don't have anything to work with. How can I guarentee that MAX-HEAPIFY will perform $\Theta(\lg k) $ operations each time?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Edit: This proof is insufficient as pointed out in comment.

I am assuming that when the author says "covers the full height of the tree", it means that the node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree.

Since the heap is a complete tree, it means that its leaves are all on the two last levels of the tree. So even if the full height of the tree is not covered, the difference with the full height will be at most 1 (like in the second case of your example), and that is why it does not change the asymptotic complexity.

Improve this answer
$\endgroup$
8
  • $\begingroup$ "the node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree". Is the statement always true. I tried <9, 8, 7, 6, 5, 4, 3>, when 5 was placed at the root, it didn't reach a leaf. Do you mean each time MAX-HEAPIFY is called, it covers until the last level or the last but one level only? Is that always true for a heap sorted in descending order? Is there a formal proof of that? $\endgroup$
    – new
    Commented Feb 24, 2021 at 7:56
  • $\begingroup$ It seems I was hasty in my claim, and it is not as simple as it looks. Moreover, "it covers until the last level or the last but one level only" is not necessarily true: I did an example with the heap <15, 14, …, 1>, and after deleting the node 10, the MAX-HEAPIFY procedure covers the height of the heap minus 2 (and not minus 1). However, your claim seems to be true for half the initial leaves of the heap (but that may be another hasty claim and needs proving). $\endgroup$
    – Nathaniel
    Commented Feb 24, 2021 at 8:54
  • $\begingroup$ If it was true for half the leaves, then since there are roughly $\frac{n}{2}$ leaves in a heap of size $n$, you would get a complexity of $\Omega(n\log n)$. $\endgroup$
    – Nathaniel
    Commented Feb 24, 2021 at 8:57
  • $\begingroup$ I was not claiming it. I was asking if it holds true always. Your example <15, 14, ....1> clearly shows that it doesn't. Then why does the answer in the link mention "every time the max element is removed and the HEAPIFY is called it will cover the full height of the tree"? And how does the summation come about? When we can't clearly state anything about how many levels MAX-HEAPIFY covers each time, then how does that summation come about? How do we then prove the running time of heapsort on an array sorted in decreasing order is $\Theta(n\lg n)$ $\endgroup$
    – new
    Commented Feb 24, 2021 at 10:00
  • $\begingroup$ Could you help me out with this? I'm trying to obtain a proof for the running time to be $\Theta(\lg n)$. If what you said earlier had been true, that would mean that mean each call to MAX-HEAPIFY won't perform full lgk operations but $ \Theta(\lg k) $ operations, right? $$ \sum_{i=1}^{n-1}\Theta( \lg{(n-i))} = \Theta\Big(\lg\Big((n-1)!\Big)\Big) = \Theta(n\lg{n}) $$ But now I don't have anything to work with. How can I guarantee that MAX-HEAPIFY will perform $\Theta(\lg k) $ operations each time? $\endgroup$
    – new
    Commented Feb 24, 2021 at 13:37
0
$\begingroup$

No comparison based sorting algorithm can be faster than $\theta(n \log n)$. On the other hand, both building the initial tree and removing items and rebalancing take at most log n steps per item.

Improve this answer
$\endgroup$
3
  • $\begingroup$ "removing items and rebalancing takes at most $\lg n$ steps each time". Yes, so each call to MAX-HEAPIFY takes $O(\lg n)$ time and there are n-1 such calls so running time of HEAPSORT is $O(n\lg n)$. But that's only an upper bound. I'm trying to prove running time for HEAPSORT on an array sorted in decreasing order is $\Theta(n \lg n)$. I'm trying to prove the lower bound as well. $\endgroup$
    – new
    Commented Feb 26, 2021 at 11:23
  • $\begingroup$ How can I prove the lower bound? As I've written in my question, how can I guarentee that MAX-HEAPIFY will perform $\Theta (\lg k) $, operations each time? (where k is the number of nodes in the modified heap each time) $\endgroup$
    – new
    Commented Feb 26, 2021 at 11:28
  • $\begingroup$ First line: No comparison based sorting etc etc. That's because there are n! possible ways an array could be sorted, and cannot distinguish all possible cases with fewer than log (n!) comparisons. $\endgroup$
    – gnasher729
    Commented Feb 26, 2021 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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