When should I use a TreeMap over a PriorityQueue a

Question

Seems they both let you retrieve the minimum, which is what I need for Prim's algorithm, and force me to remove and reinsert a key to update its value. Is there any advantage of using one over the other, not just for this example, but generally speaking?

Answer 1

One of the differences is that remove(Object) and contains(Object) are linear O(N) in a normal heap based PriorityQueue (like Oracle's), but O(log(N)) for a TreeSet/Map.

So if you have a large number of elements and do a lot of remove(Object) or contains(Object), then a TreeSet/Map may be faster.

Answer 2

I may be late to this answer but still.

They have their own use-cases, in which either one of them is a clear winner.

For Example:

1: https://leetcode.com/problems/my-calendar-i TreeMap is the one you are looking at

2: https://leetcode.com/problems/top-k-frequent-words you don't need the overhead of keys and values.

So my answer would be, look at the use-case, and see if that could be done without key and value, if yes, go for PQueue else move to TreeMap.