gjaiswal108's blog

Multiset vs priority_queue
By gjaiswal108, history, 5 years ago, In English

The thing we can do with priority queue, can also be done with multiset. Then what is the quality that's unique in priority queue? Can anyone give any example where multiset fails and only priority queue works?

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

»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

More complicated data structures (those with more functionality) are usually slower. I think that's the case here too. Priority queue is faster.

→ Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

multiset has higher constant factor(for rotations and whatever) you can read more about how red-black trees works

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Others already compared tree data structures to priority queue. I want to add that I've had plenty TLE submissions with multiset I had to use map for counting number of appearance instead. multiset and multimap can be very slow when there are too many duplicated keys so keep that in mind when you use them.

→ Reply