Is destructuring a heap (taking down a heap) also O(n) like building a heap? If so, can the selection problem be solved by this method in O(n) time?

Question

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?

Answer 1

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.

Answer 2

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.