Map Vs Priority queue with pop operation

Question

Hello

I have a doubt in selecting map vs priority queue.

I am having my own class whose data need to be stored. I need 3rd largest data from all records.

Isn't it good to go with map and find third last data compared to using priority queue and popping out largest data two times?

Answer 1

If you need the map for other map-type things then it's probably not worth building a priority queue. Constructing a heap/priority queue is O(n log n) while finding the 3rd largest element in a map is O(n).

If you need to find the third largest element a lot you could consider building a wrapper class around map, that also keeps a priority queue of size 3, and everytime you add something to the map you queue and dequeue one item in the priority queue.

Just a priority queue could be a good fit too, it really depends on what the rest of the program is doing. :)

Answer 2

Erm the only example I can think of off the top of my head is graph theory related..

Imagine you have a map of all major cities and railroad connections in between. You start in New Delhi and want to get to Vienna, so you enumerate all the neighboring cities of New Delhi and add them to the priority queue, where the priority == distance to Vienna. Then you can pop an element off the queue and it's the one that's most likely to get you to Vienna fastest. Rinse and repeat, you are now in Ludhiana, add neighbors to queue, pop...
(path-finding on digraph)

I'm not sure when I've last needed a priority queue in real-life code.

Answer 3

Thanks Schindlabua

If possible , could you please give some example where priority queue is chosen over map ?

Everytime I think about priority queue , I gets confused that map also gives me max data or min data by default and I don't have to pop out also anything