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

Feudatory

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

Votive

which is better extending PriorityQueue class or using a wrapper for putting unique elements? – Som

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.

Cralg

Might be helpful to add why someone wouldn't use a TreeSet. (peek operations on a TreeSet are O(logn) whereas a PriorityQueue is constant; popping the head is slightly more expensive in a TreeSet) – Eldoria

Answer 3

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

Successful

For this to work, the comparison function should be consistent with equality, which is not always the case. For example a multi-state A* search, where the open-state Q compare on weight and equality on the node, which are not related to each other. – Minium

@LaurentGrégoire you could construct such as case, however given the javadoc of compareTo states it should be consistent with equals, its a fairly serious hack to not do this. – Successful

Answer 4

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.

Lustre

Having in consideration that PriorityQueue is a Binary Heap and that its contains() method runs in O(n), I could hardly think of anything more inefficient than this bit of code. – Thereof

Answer 5

Override methods hashCode() and equals(Object obj) to avoid duplicate and use method contains to check if the object exists or not.

class Element {
    int i, j, distance;
    public Element(int i, int j, int distance) {
        super();
        this.i = i;
        this.j = j;
        this.distance = distance;
    }
    @Override
    public int hashCode() {
        return Objects.hash(i, j);
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        
        Element element = (Element) obj;
        return Objects.equals(i, element.i) && Objects.equals(j, element.j) ;
    }
    @Override
    public String toString() {
        return "Element [i=" + i + ", j=" + j + ", distance=" + distance + "]";
    }
}

Check like below

PriorityQueue<Element> pq = new PriorityQueue<>((a, b) ->  (a.distance == b.distance ?  a.i == b.i ? a.j - b.j : a.i - b.i : a.distance - b.distance));
pq.add(new Element(i1, j1, d1)); // element values

Element e2 = new Element(i2, j2, d2);
if(!pq.contains(e2)) {
    pq.add(e2);
}

Elisabethelisabethville