1

Now that we have Red Black trees and AVL trees, it means that inserts and deletes take log(N) time. (We also note that find_min() would take log(N) time).

Comparing these to heap, we have same complexities. However the above mentioned trees are BST so we can search in log(N) there. All in all I don't understand how heaps can be useful?

3
  • 2
    Why would the mechanism for search have any bearing on the usefulness of heaps? Seems like you're conflating performance with utility. Commented Oct 31, 2016 at 19:11
  • No search is additional property of BST. So they can do all that a heap can do plus something...that is what I wanted to say. Commented Oct 31, 2016 at 19:12
  • OK. So why would that make a heap useless? Your logic fails. Commented Oct 31, 2016 at 19:15

1 Answer 1

4

A heap is always perfectly balanced. A Red Black tree has a bound on how unbalanced it can be, but it will still often be less than perfectly balanced. While this won't affect the Big O value of the operations, it doesn't mean that there isn't a performance difference; there's a very wide range of possible performance among any given Big O value, and improvements within that range are still very often useful in practical application.

9
  • Oh, I see. You're talking about this Heap. Commented Oct 31, 2016 at 19:18
  • @RobertHarvey Yes.
    – Servy
    Commented Oct 31, 2016 at 19:18
  • @Servy Ok so you mean that although both are log(N) one might be 2 log(N) and one might be 10log(N). Am I getting it right? Commented Oct 31, 2016 at 19:24
  • @ArghyaChakraborty The differences would be more complex than just a constant multiplier, but yes, that's the general idea.
    – Servy
    Commented Oct 31, 2016 at 19:25
  • 4
    @ArghyaChakraborty: What? Commented Oct 31, 2016 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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