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?

  • 2
    Why would the mechanism for search have any bearing on the usefulness of heaps? Seems like you're conflating performance with utility. – Robert Harvey Oct 31 '16 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. – User Not Found Oct 31 '16 at 19:12
  • OK. So why would that make a heap useless? Your logic fails. – Robert Harvey Oct 31 '16 at 19:15

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.

  • Oh, I see. You're talking about this Heap. – Robert Harvey Oct 31 '16 at 19:18
  • @RobertHarvey Yes. – Servy Oct 31 '16 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? – User Not Found Oct 31 '16 at 19:24
  • @ArghyaChakraborty The differences would be more complex than just a constant multiplier, but yes, that's the general idea. – Servy Oct 31 '16 at 19:25
  • 4
    @ArghyaChakraborty: What? – Robert Harvey Oct 31 '16 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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