[SOLVED] What is the time complexity of clearing a heap?

What is the time complexity of clearing a heap?

I have googled for lots of websites and they all say "the time complexity of clearing a heap is O(n log n)." The reason is:

Swapping the tailing node the root costs O(1).
Swapping "the new root" to suitable place costs O(level) = O(log n).
So deleting a node (the root) costs O(log n).
So deleting all n nodes costs O(n log n).

In my opinion, the answer is right but not "tight" because:

The heap (or its level) becoming smaller during deleting.
As a result, the cost of "swapping the new root to suitable place" becomes smaller.
The aforementioned reason of "O(n log n)" does not embody such change.

The time complexity of creating a heap is proved as O(n) at here.

I tend to believe that the time complexity of clearing a heap is O(n) as well because creating and clearing is very similar - both contain "swapping node to suitable position" and "change of heap size".

However, when considering O(n) time for clearing a heap, here is a contradiction:

By creating and clearing a heap, it is possible to sort an array in O(n) time.
The lower limit of time complexity of sorting is O(n log n).

I have thought about the question for a whole day but still been confused.

What on earth clearing a heap costs? Why?

Solution

As you correctly observe, the time taken is O((log n) + (log n-1) + ... + (log 2) + (log 1)). That's the same as O(log(n!)), which is the same as O(n log n) (proof in many places, but for example: What is O(log(n!)) and O(n!) and Stirling Approximation).

So you're right that the argument given for the time complexity of removing every element of a heap being O(nlog n) is wrong, but the result is still right.

Your equivalence between creating and "clearing" the heap is wrong. When you create the heap, there's a lot of slack because the heap invariant allows many choices at every level and this happens to mean that it's possible to find a valid ordering of the elements in O(n) time. When "clearing" the heap, there's no such slack (and the standard proof about comparison sorts needing at least n log n time proves that it's not possible).