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?


closed as unclear what you're asking by D.W., Luke Mathieson, Nicholas Mancuso, Rick Decker, Tom van der Zanden Feb 16 '15 at 13:42

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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

  • $\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.