Strange ordering in PriorityQueue in Java

Question

I am trying to use priority queue to keep an ordered list of integers. in a simple exaple like this:

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(3000);
queue.offer(1999);
queue.offer(999);
for(Integer i : queue)
    System.out.println(i);

This prints

999
3000
1999

This is not what I am expecting considering natural odering.

I simply want to iterate without removing or adding through the queue (which serves as a sorted list) WITH ordering. Can I still do that in a simple manner?

Why not use a SortedList or a SortedSet instead? – Justin Jun 10 '12 at 21:25 — Justin, Jun 10 '12 at 21:25

score 8 · Accepted Answer · answered Jun 10 '12 at 21:26

PriorityQueue is a collection optimized for finding the tail or head value quickly, using a partially ordered tree structure called heap (look it up on wikipedia). If you pop the elements, they will be ordered. If you want to iterate, use for example a SortedSet instead, which also stores the elements sorted.

score 4 · Answer 2 · answered Jun 10 '12 at 21:28

This is a very sneaky problem with PriorityQueue: to quote the Api

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

Use Poll instead to get the head which will be in order

Strange ordering in PriorityQueue in Java

2 Answers2

Linked