Java PriorityQueue and Comparator Not Ordering correctly

Question

I am new to Java and am trying to implement a priority queue with a custom comparator. I want to put the Sentences in the queue and have them removed in order to highest score.

For the comparator class I have:

public class SentenceScoreComparator implements Comparator<Sentence> {

@Override
public int compare(Sentence o1, Sentence o2) {
    if (o2.getScore() > o1.getScore()) return -1;
//fixed typo
    if (o2.getScore()  < o1.getScore()) return 1;
    return 0;
}

}

I then print out the sentences like so:

PriorityQueue<Sentence> allSentences = new PriorityQueue<Sentence>(new SentenceScoreComparator());
//add sentences

for(Sentence s :allSentences){
            System.out.println(s.getScore()); 
        }

but they are not in order

0.34432960587450223
0.47885099912108975
0.10991840331015199
0.36222267254836954
0.05164923572003221
0.5366117828694823
0.3891453014131773
0.0961512261934429
0.5566040852233918
0.5079687049927742
0.7628021620154812
0.6023121606121791
0.25695632228681914
0.15701049878801304
0.1260031244674359
0.36516025683986736
0.3846995962155155

I checked that the queue is using the comparator with the correct comparator method. Can someone explain what I am missing?

Jean Logeart · Accepted Answer · 2016-03-23 20:05:02Z

3

You have a typo in the comparator in the second if where o2 score is compared to itself.

Replace it with:

@Override
public int compare(Sentence o1, Sentence o2) {
    return Double.compare(o1.getScore(), o2.getScore());
}

On top of that, as bradimus answered, PriorityQueue does not guarantee any sorted traversal. Use a regular list and sort it for that.

answered Mar 23, 2016 at 20:05

Jean Logeart

54.1k11 gold badges88 silver badges120 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

John Down Over a year ago

Thanks. I don't know how I missed that

bradimus · Accepted Answer · 2016-03-23 20:15:56Z

3

PriorityQueue never promised to traverse them in order. From the javadocs:

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. 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()).

edited Mar 23, 2016 at 20:15

answered Mar 23, 2016 at 20:03

bradimus

2,5341 gold badge19 silver badges24 bronze badges

Collectives™ on Stack Overflow

Java PriorityQueue and Comparator Not Ordering correctly

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related