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?
-
2Why would the mechanism for search have any bearing on the usefulness of heaps? Seems like you're conflating performance with utility.Robert Harvey– Robert Harvey2016年10月31日 19:11:50 +00:00Commented 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.User Not Found– User Not Found2016年10月31日 19:12:32 +00:00Commented Oct 31, 2016 at 19:12
-
OK. So why would that make a heap useless? Your logic fails.Robert Harvey– Robert Harvey2016年10月31日 19:15:44 +00:00Commented Oct 31, 2016 at 19:15
1 Answer 1
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– Robert Harvey2016年10月31日 19:18:35 +00:00Commented 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?User Not Found– User Not Found2016年10月31日 19:24:08 +00:00Commented 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– Servy2016年10月31日 19:25:08 +00:00Commented Oct 31, 2016 at 19:25
-
4@ArghyaChakraborty: What?Robert Harvey– Robert Harvey2016年10月31日 19:27:09 +00:00Commented Oct 31, 2016 at 19:27