3

Since a Balanced BST would take O(log(n)) time is extracting the max (by extracting I mean both find and delete Max element). On the other hand Max-heap would also take O(log(n)) time in extracting the max element.

Does anyone of them has cutting edge over the other in Extract-Max operation?

gsamaras
  • 71,951
  • 46
  • 188
  • 305
  • I know that. But what if we want to perform extract-max kinda operation. So which one will be the suitable data structure a balanced bst or max heap. –  May 09 '17 at 13:16
  • 1
    In some special cases `BST` would take only one operation more than `Heap` otherwise both can extract max in same number of operation. But that one more operation is negligible . – Sanket Makani May 09 '17 at 13:20
  • 2
    @GAURANGVYAS Finding the Right most node of the Balanced Bst would take O(log(n)) and performing a delete operation would take O(1). –  May 09 '17 at 13:21
  • Okay finding max element will take O( log n ) time, as we need to find the rightmost element and then deletion would take O(1) as it would be a leaf node or a node with only one child. Correct@ Sanket Makani and @Satyendra – GAURANG VYAS May 09 '17 at 13:24

1 Answers1

0

When thinking of data structures, you should take into account their complexities, both of time and space. Here space is the same, so let's focus on time:

Balanced BST:

balanced BST maintains h = O(lg n) ⇒ all operations run in O(lg n) time.

Max-Heap:

Find max O(1), Delete max O(lg n)

which means that their time complexities are also the same.

Also by reading this answer, you draw the same conclusion:

...a max-heap or a binary tree is a good fit.

However, note that balancing an already constructed BST is an O(n) operation (Balancing a BST). So if I had to do that too, then I would go for a max heap.

For advanced usage, read Which data structure to use for accessing min/max in constant-time?

Sources: 1, 2.

Community
  • 1
  • 1
gsamaras
  • 71,951
  • 46
  • 188
  • 305
  • So whats your conclusion on this? –  May 09 '17 at 13:45
  • So for that operation both are fine when it comes to efficiency. If I were you, I would see which is easier to be implemented, or whether I have access to a library that provides such a data structure. For example, if I am writing in [tag:c++] and there is a library that I like, which provides a heap, I would go for that! – gsamaras May 09 '17 at 13:47
  • I think balancing the tree is an overhead. And I am not concerned about simplicity of implementation for now. –  May 09 '17 at 13:51
  • Oh I thought the question was, that given I have these data structures already, what's better @SatyendraYadav. Yes it is, let me update my answer. By the way, you can ask a new question, instead of editing the one you have already posted and got an answer for it. That way we maintain the compactness of the posts! =) – gsamaras May 09 '17 at 13:58
  • @gsamaras You have provided a link about balancing a BST , but there the user balances a whole tree, which is initially unbalanced. But in this case rebalancing is required only after delete operation(and that too only in some cases) and will not take O(n) time. Balancing a previously unbalanced tree is different from balancing that is performed in this case. – GAURANG VYAS May 09 '17 at 14:01
  • Correct @GAURANGVYAS! That's another question Mr. Yadav. – gsamaras May 09 '17 at 14:02