If we can build up a heap with time O(n), can we take down a heap also by O(n)? (by delete-max repeatedly).

Intuitively, it may feel it is, because it is like the reverse of build it up.

(Building a heap can be O(n) -- in Wikipedia).

If building a heap is O(n) in the worst case, including the numbers are all adding by ascending order, then taking the heap down is exactly the "reverse in time" operation, and it is O(n), but this may not be the "worst case" of taking it down.

If taking down a heap is really O(n), can't the selection problem be solved by building a heap, and then taking it down (k - 1) time, to find the kth max number?

  • 2
    $\begingroup$ Taking down the heap is not really the reverse of heapify, it is the reverse of starting with an empty heap and adding elements one by one. Both of these are n log n $\endgroup$ – Matthew C Mar 21 '20 at 13:28
  • $\begingroup$ @MatthewC building a heap is really O(n). See en.wikipedia.org/wiki/Binary_heap#Building_a_heap $\endgroup$ – nonopolarity Mar 21 '20 at 13:52
  • 1
    $\begingroup$ What do you mean by "take down"? Note that building heaps in linear time is not accomplished by repeated "push". $\endgroup$ – Raphael Mar 21 '20 at 16:27
  • $\begingroup$ @nonpolarity That is heapify (makeHeap, or whatever you like to call the process of transforming an array into a heap). $\endgroup$ – Matthew C Mar 21 '20 at 16:51

Delete-max is $O(\log n)$, so you have $O(n) + k O(\log n)$ which is $O(n)$ for fixed $k$. But if $k$ is not fixed, it can be up to $\frac{n}{2}$ (if it's greater, just use a min-heap instead of a max-heap), and $O(n) + \frac{n}{2} O(\log n) = O(n \log n)$.

In fact, if there was some tricky way to do what you want, you would solve sorting in $O(n)$, not just selection, which is known to be impossible.

  • $\begingroup$ that's true... I "accidentally" solved the sorting problem with a O(n) method $\endgroup$ – nonopolarity Mar 21 '20 at 17:21
  • $\begingroup$ that's interesting... I usually take a shorter time taking my Mac Mini apart than to re-assemble it $\endgroup$ – nonopolarity Mar 21 '20 at 17:31

Building a heap is O(n).

Taking the first item from a heap and then re-arranging things so it is a heap again is O (log n), and since you need to do this n time is O (n log n).

Of course you can just take one element of the heap after the other in O(n), but they won't be in sorted order. And building a heap can be done in O(n) because you add n/2 items to the lowest level of the heap when it has height 1, n/4 to the second lowest level of the heap when it has height 2, n/8 when it has height 3, and so on. And n/2 * 1 + n/4 * 2 + n/8 * 3 ... < n.

  • $\begingroup$ I guess you are saying there is no smart way (known) to take it down so that it is O(n) $\endgroup$ – nonopolarity Mar 21 '20 at 14:50
  • $\begingroup$ @nonopolarity You are assuming that there is a way to take it down in $O(n)$ because you can build it in $O(n)$. Just as the build operation requires you to have all $n$ elements on hand to create the heap, you can delete the heap in $O(n)$ time but only if you are deleting all $n$ elements as well. $\endgroup$ – Throckmorton Mar 21 '20 at 15:09
  • $\begingroup$ @Throckmorton is it true that by the same argument, then it could sound like you have to build the heap by O(n log n)? $\endgroup$ – nonopolarity Mar 21 '20 at 15:55
  • $\begingroup$ If you are building the heap by inserting elements one at a time, then it is $O(n\log n)$ $\endgroup$ – Throckmorton Mar 21 '20 at 16:03
  • $\begingroup$ "I guess you are saying there is no smart way (known) to take it down so that it is O(n) " You can take it down in O(1); just ignore the argument and return the empty heap. This won't help you with the selection problem, of course. $\endgroup$ – Alexey Romanov Mar 21 '20 at 16:17

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.