PriorityQueue changes elements positions on poll()

Question

I got some problem with using a priority queue. Unfortuneatly my google research didn't have a result :( I hope someone can help me.

I'm using a priority queue to sort some objects by a specific attribute called "reachabilityDistance" which is a simple double value. Inserting objects into the queue works fine and results in a correct ordering. But then I want to poll the first object of the queue and the order of the other object changes even if their values are staying the same. What is wrong with that?

private PriorityQueue<ClusteringObject> orderedSeedQueue;
...
orderedSeedQueue = new PriorityQueue<>(clusteringObjects.size(), new ReachabilityObjectComperator());
while (!orderedSeedQueue.isEmpty()) {
            clusteringObject = orderedSeedQueue.poll();
            calculateNeighborhood(clusteringObject, clusteringObjects);
            clusteringObject.setProcessed();
            clusteringObject.setCoreDistance(minNeighbors);
            resultClusterList.add(clusteringObject);
            updateSeedQueue(clusteringObject.getNeighbors(), clusteringObject);
        }

This is the code snippet where I am working with my priority queue. In the updateSeedQueue method some values are inserted respectivly updated in that queue (remove and add again). This works fine for me but every time the poll() is performed all correct sorted entries are getting a wrong order.

Here is my comparator:

public class ReachabilityObjectComperator implements Comparator<ClusteringObject> {

@Override
public int compare(ClusteringObject x, ClusteringObject y) {
    if (x.getReachabilityDistance() < y.getReachabilityDistance()) {
        return -1;
    } else if(x.getReachabilityDistance() > y.getReachabilityDistance()) {
        return 1;
    } else {
        if(x.getMetadataIndex() < y.getMetadataIndex()) {
            return -1;
        } else if(x.getMetadataIndex() > y.getMetadataIndex()) {
            return 1;
        } else {
            return 0;
        }
    }
}

}

So my question again: why does the poll() changes the ordering of the remaining objects in this queue?

Answer 1

PriorityQueue only claims to make the first entry in correct order. If you iterate over the PriorityQueue you can see all but the first element in any order and it may change as you add/remove entries.

From the Javadoc for PriorityQueue

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

If you need correct ordering at all times I suggest using TreeSet.

NavigableSet<MyType> orderedSeedQueue = new TreeSet<>(new MyComparator());
// add elements

while(!orderSeedQueue.isEmpty()) {
     firstItem = orderSeedQueue.pollFirst();

However, depending on your use case it may be simpler to sort them.

List<MyType> types = ...
Collections.sort(types, new MyComparator());
for(MyType t : types) { // in sorted order