Java: PriorityQueue returning incorrect ordering from custom comparator? [duplicate]

Question

I've written a custom comparator to compare my node classes, but the java priority queue is not returning my items in the correct order.

Here is my comparator:

public int compare(Node n1, Node n2){

    if (n1.getF() > n2.getF()){
        return +1;
    }
    else if (n1.getF() < n2.getF()){
        return -1;
    }
    else {  // equal
        return 0;
    }
}

Where getF returns a double. However after inserting several Nodes into the priority queue, I print them out using:

while(open.size() > 0) {
    Node t = (Node)(open.remove());
    System.out.println(t.getF());
}

Which results in:

6.830951894845301
6.830951894845301
6.0
6.0
5.242640687119285
7.4031242374328485
7.4031242374328485
8.071067811865476

Any ideas why this is so? Is my comparator wrong? Thanks.

Mike

Answer 1

How are you printing out those values? I don't think the iterator from PriorityQueue provides the same ordering assurances that the overall class does, so potentially if you're doing

for(Node n : queue) {
System.out.println(n.getF());
}

You'll be getting unordered output. The ordering assurance only applies to offer, take, poll, peek, and possibly some other methods.

There's a special mention on the iterator in the javadocs for priority queue http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html