CODEWITHSUNDEEP
algorithmdata-structurestime-complexity
user3284843
user3284843

Reputation: 3

Which data structure can handle these demands?

I need a data structure that can handle these demands: * retrieve minimum value in O(lg(n)) * retrieve maximum value in O(lg(n)) * insert a value to the data structure in O(lg(n))

for the max and insert- I think a max binary heap can handle this, however it won't work for the min, because the minimal value can be in every leaf that is about n/2 values - in other words O(n) ? please tell me if I'm wrong about this.

Also I'll be very happy if someone can help me find the needed data structure for these demands.

Many thanks

Upvotes: 0

Views: 97

Answers (4)

Jim Mischel
Jim Mischel

Reputation: 134125

Another option is a skip list, which will give you the minimum in O(1), insert in O(log n), and get the max in O(log n).

Upvotes: 1

dwschrute
dwschrute

Reputation: 104

AVL tree is what you are looking for!

It is basically a BST, but maintained to be balanced all the time by doing actions called rotation. Being balanced all the time, the height of the tree would be lg(n), thus searching for max and min at most takes O(height) = O(lgn), and inserting also takes O(lgn) time.

Take a look at this lecture, it explains very clearly how AVL tree works, how to maintain and how come it costs the time I above mentioned. You can also just google for AVL tree for further information.

Upvotes: 0

yuri kilochek
yuri kilochek

Reputation: 13589

Min-max heap is what you are looking for.

Upvotes: 3

templatetypedef
templatetypedef

Reputation: 373392

You can use a balanced binary search tree to do this. Inserting values takes only O(log n) time in a balanced BST, and you can read off the min or max values by finding the leftmost and rightmost nodes in the tree, respectively.

Alternatively, you could look up various implementations of double-ended priority queues, which might also help here. They're more complex than balanced BSTs and most languages don't ship with libraries for them, though they are more appropriately tuned to your needs.

Hope this helps!

Upvotes: 2

Related Questions