Java PriorityQueue behaviour with 3 elements in the Queue

Question

As per the definition of PriorityQueue, it says :

The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.

But when I am trying with 3 elements in the Queue, the elements does not appear to be sorted properly.

    Queue<Integer> q2 = new PriorityQueue<Integer>();
    q2.add(9);
    q2.add(7);
    q2.add(8);

    Iterator<Integer> i = q2.iterator();
    while(i.hasNext()){
        Integer e = i.next();
        System.out.println(e);
    }

Output :

7
9
8

[edit] If the number of elements is 4, the sorting appears to be correct

    q2.add(9);
    q2.add(7);
    q2.add(8);
    q2.add(5);

    Iterator<Integer> i = q2.iterator();
    while(i.hasNext()){
        Integer e = i.next();
        System.out.println(e);
    }

Outputs:

score -1 · Answer 1 · answered May 16 '17 at 05:22

The problem is that you are using Iterator which does not guarantee any order during traversal of the queue. The Javadoc of PriorityQueue says:

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

When you poll the queue, you'll get the correct order:

while (!q2.isEmpty()) {
  System.out.println(q2.poll());
}

Why the downvote? Is something wrong with this answer? – Stefan Ferstl May 16 '17 at 07:29 — Stefan Ferstl, May 16 '17 at 07:29

Java PriorityQueue behaviour with 3 elements in the Queue

1 Answers1