dumbguy's blog

stl set vs min_heap
By dumbguy, history, 7 years ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is O(1). Loot here — complexity of set.begin() is constant.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Both are O(1), just make sure there aren't any duplicates, otherwise, you'll have to use min heap over set.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    multiset?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      yep, I was just drawing his attention that "set" will have only one copy of distinct elements in contrast to a heap (priority_queue)

      → Reply