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?