How to configure Java Priority Queue to ignore duplicates?

Question

I thought add() is supposed to ignore duplicates, but my output has duplicates. How do I not store duplicates?

I would also like to know how the priority queue checks if two elements are duplicates. I'm guessing it's using the comparator equals, but I just want to be sure.

Thanks

Answer 1

Here is a part from PriorityQueue Javadoc:

This queue orders elements according to an order specified at construction time, which is specified either according to their natural order (see Comparable), or according to a Comparator, depending on which constructor is used.

So yes, PriorityQueue uses Comparator (if you specified it as a constructor argument) or uses compareTo(...) method (elements must implement Comparable interface).

PriorityQueue allows duplicates. So if you want to avoid that, you need to implement your own version of Queue. You can find very elegant way, how to do that in "Effective Java", page 85. Alternatively you might extend PriorityQueue class and override add method (this is a perfect place to put contains(...) check).

Answer 2

A PriorityQueue in Java does not have any restriction with regard to duplicate elements. If you want to ensure that two identical items are never present in the priority queue at the same time the simplest way would be to maintain a separate Set in parallel with the priority queue. Each time you want to insert an element into the priority queue you can check if the set contains it already, if not, then add it to both the set and the priority queue. Whenever you remove an element from the priority queue then just remove that element from the set as well.

Alternatively, depending on which operations you intend to perform on the priority queue, and how equality is defined in your case, it might be viable to replace it with a single TreeSet instead since that will still allow you to perform all important operations that you would have access to in a priority queue while it additionally does not allow duplicates.