How to configure Java Priority Queue to ignore duplicates?

Solution 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).

Solution 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.

Solution 3:

The following sample implementation

import java.util.PriorityQueue;

public class NoDuplicates<E> extends PriorityQueue<E> 
{
    @Override
    public boolean offer(E e) 
    {
        boolean isAdded = false;
        if(!super.contains(e))
        {
            isAdded = super.offer(e);
        }
        return isAdded;
    }
    public static void main(String args[])
    {
        PriorityQueue<Integer> p = new NoDuplicates<Integer>();
        p.add(10);
        p.add(20);
        p.add(10);
        for(int i =0;i<=2;i++)
        {
            System.out.println(p.poll());
        }
        
    }
}

results in

10
20
null

which shows that it doesn't add a duplicate element 10.

Solution 4:

Sets are the only things which ignore duplicates. Lists and queues do not. (LinkedList is a Queue)

If you want to drop duplicates you can check whether the entry you take() is the same as the previous and ignore it. You can do the comparison any way you like. ;)