Блог пользователя dumbguy

stl set vs min_heap
Автор dumbguy, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить