What is the complexity for popping all n elements from a heap?

Question

To build a heap, it's frequently mistaken that O(n log n) is the strict upper bound, but it's actually O(n).

I want to say that popping all n elements from a heap is O(n log n), but based on what I know about complexity for building a heap, I'm hesitant, and I think it might be O(n) for the same reason building a heap is O(n).

Is this correct?

Each time we pop, we need to find a new root, and the heapify function will take O(h) time where h is the height of the binary tree. For a balanced binary tree like what a heap uses, h = log_2(n). But the number of nodes decreases one by one for each pop, so h should decrease.

So if I were to calculate the complexity I would do something like

O(log_2(n) + log_2(n-1) + ... + log_2(1))
= O(log_2(n * (n-1) * ... * (1))
= O(log_2(n^n)) 
= O(n log_2(n)

But is this the actual strict upper bound?

Answer 1

Imagine there was a way to do n pops from a heap in time O(n). That would give you a comparison-based sorting algorithm that runs in time O(n) as follows:

• Build the heap in time O(n) using heapify.
• Use the O(n)-time algorithm to do n pops.

However, this is impossible because all comparison-based sorting algorithms run in time Ω(n log n) on average and in the worst-case.

In fact, this argument shows that the cost of n pops must have a worst-case runtime of Ω(n log n), so that upper bound is tight in the worst case.