0

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?

Zhicheng Zhang
  • 59
  • 1
  • 7
  • The question is, while you are deleting the heap, would you like to maintain the ordering of the heap? A heap can be destroyed in linear time, it only has linear number of nodes and edges -- but if what about when you would like to maintain the order for the head? – user73236 May 16 '20 at 05:44

1 Answers1

3

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

Paul Hankin
  • 54,811
  • 11
  • 92
  • 118
  • I have read the last paragraph of your answer several times and comprehend (maybe?) what you want to express. – Zhicheng Zhang May 16 '20 at 06:37
  • When offer to create a heap, the proper location of the new node is random - maybe at root/leaf/middle, which means the **WORST** time complexity is O(log n). – Zhicheng Zhang May 16 '20 at 06:38
  • When poll to clear a heap, a leaf node (near max value in min-heap) is swapped to root and then swap to find a proper location. Intuitively, it will swap at least log n - 1 level, which means the **AVERAGE** time complexity is O(log n). – Zhicheng Zhang May 16 '20 at 06:38
  • Even these both offer and poll costs O(log n) of time, because of such tiny difference, when accumulating them as to create and clear, the time complexity becomes different - **create as O(n) vs. clear as O(n log n)**. – Zhicheng Zhang May 16 '20 at 06:39