World's most popular travel blog for travel bloggers.

[Answers] What will trigger a worst time search for a binary heap and what is the run time?

, , No Comments
Problem Detail: 

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?

Asked By : John Swoon

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback