CODEWITHSUNDEEP
algorithmsortingheapheapsortbinary-heap
Zhicheng Zhang
Zhicheng Zhang

Reputation: 69

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:

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

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:

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

What on earth clearing a heap costs? Why?

Upvotes: 0

Views: 2305

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58399

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).

Upvotes: 3

Related Questions