I thought if the values in a max or min heap is monotonically increasing or decreasing, then this will trigger a worst case run time of $\mathcal{O}(n)$ because you will have to go through each and every single node to get to the value you want.

However, many sources state that heap has a worst case of $\mathcal{O}(n\log n)$ for (all?) transactions.

I don't see how you can do $n\log n$ for a monotonically increasing binary heap.

Can someone clarity?

  • 2
    $\begingroup$ You apparently don't know how heaps work. The neat thing is that it does not have to look at all entries due to well-chosen and maintained invariants. $\endgroup$ – Raphael Dec 16 '14 at 8:09
  • 1
    $\begingroup$ Also, worst-case running time for what operation? For a lookup? To build the heap? The running time depends on the operation you are doing. You can't talk about "the running time for a heap" -- that doesn't make sense. $\endgroup$ – D.W. Feb 6 '15 at 22:44

Heaps are maintained so that they are always balanced. A heap containing $n$ elements will have height $O(\log n)$. All operations on heaps take time linear in the height.

| cite | improve this answer | |
  • $\begingroup$ doh! confused binary heap with binary tree $\endgroup$ – Olórin Dec 16 '14 at 1:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.