   SOLVED  - data structure needed -  pop min and max at O(1), insert at O(logn)
  hi,I need a data structure that can keep hold of objects with an order between them and at any point get the smallest object at O(1) or the largest object at O(1).in addition id like to add/remove objects at O(logn).im abit rusty on datastructures, me thinks a heap can get minimum, maybe i need two heaps one for min and one for max?id prefer not to insert/remove twice (yes i know it doesnt affect the complexity but it will make my puzzle solver much slower).does STL have heaps?  (i always only used list/vector/string...) maybe a sorted data structure like an AVL tree?   does STL have AVL trees?thanks,Iftah.edit: changed subject to better reflect need.[Edited by - Iftah on December 13, 2005 5:02:35 PM]
  I believe the STL set and map (which are usually red-black trees) achieve these performance characteristics. I also believe the other related trees (AVL, splay, a-b) have similar performance, if you want to customize the precise implementation.   ;  The standard library provides heap operations (generic algorithms std::push_heap/pop_heap/make_heap/sort_heap/is_heap) that allow you to build heaps with any container that support random access iterators such as arrays, std::vector, std::deque, std::basic_string.There is no explicit AVL tree in the standard library but the sorted associative containers such as (std::(multi)set/map) could be implementated "in terms of an AVL tree" however in practice it's almost always a red-black tree.   ;  thanks for the replies,associative containers provide insert/pop at O(logn), but can they also provide getting the min/max at O(1) ?(no biggy if they dont, ill use map anyway)i havent learned about red-black trees (my lecturer was a joke, we barely learnt half the subjects we were supposed to) but heard they have same complexity and features as AVL.   ;  You can use the standard map (or extended hash_map) and then just keep track of the min and max separately.;  Hmm... aren't there complexity guarantees given for begin() and rbegin() in the Standard? I suppose they might be logarithmic in some implementations in Sorted Associative Containers' case (that is, map and set), but it wouldn't make much sense - keeping track of them adds such a minimum overhead that it should be totally worth it. So if they are O(1), no need to keep track of min and max separately.   ;  I imagine begin and end are O(1) but they will not necessarily point to the min & max.  We can imagine the end is a "null-iterator" and begin will give you the root of the tree.  But there's another problem, map is unordered.To accomplish an ordered set with O(log) look-ups you need to index a list.   ;  Nope; std::map and std::set are models of the concept Sorted Associative Container and are most certainly sorted in a well-defined way. This means that iterating through a set is guaranteed to yield the elements in the order the  ordering relation imposes, so begin() always points to the minimum, and rbegin() always points to the maximum.EDIT: The begin(), end(), rbegin(), and rend() operations are guaranteed amortized constant time (as noted here and here).   ;Quote:Original post by Shannon BarberI imagine begin and end are O(1) but they will not necessarily point to the min & max.I concur if you're refering to std::[multi_]map's value parameter. std::[multi_]map/set are all, however, sorted by key value.int source[] = { 4 , -2 , 2 };std::set< int > sorted( source , source + 3 );std::set< int >::const_iterator i = sorted.begin();assert( *i++ == -2 );assert( *i++ == 2 );assert( *i++ == 4 );assert( i == sorted.end() );;Quote:Original post by Iftahhi,I need a data structure that can keep hold of objects with an order between them and at any point get the smallest object at O(1) or the largest object at O(1).in addition id like to add/remove objects at O(logn).im abit rusty on datastructures, me thinks a heap can get minimum, maybe i need two heaps one for min and one for max?id prefer not to insert/remove twice (yes i know it doesnt affect the complexity but it will make my puzzle solver much slower).does STL have heaps?  (i always only used list/vector/string...) maybe a sorted data structure like an AVL tree?   does STL have AVL trees?thanks,Iftah.What you are looking for is called a Deap or a Min-Max heap.   