Suppose i only need to get the minimum element at every instance (there is constant addition and removal of items).
Which would be optimum in terms of time complexity? stl set or min_heap (implemented as priority_queue)
I know min_heap gets the minimum element in O(1). But what about stl set? Is it O(1) or more than O(1).
Thanks
It is
O(1)
. Loot here — complexity ofset.begin()
is constant.Both are O(1), just make sure there aren't any duplicates, otherwise, you'll have to use min heap over set.
multiset?
yep, I was just drawing his attention that "set" will have only one copy of distinct elements in contrast to a heap (priority_queue)