Queue not ordering naturally

Question

Possible Duplicate:
Why is this strange order happens in PriorityQueue in java?

Please, see the code below:

public static void main(String[] args) {
    Queue<String> q = new PriorityQueue<String>();
    q.offer("car");
    q.offer("airplane");
    q.offer("bicycle");
    Iterator<String> i = q.iterator();
    while(i.hasNext())
        System.out.print(i.next() + " ");
}

Can someone explain me why the output is

airplane car bicycle

instead of

airplane bicycle car

?

Since in the API it says that the elements of the priority queue are ordered according to their natural ordering.

Just found this: [Why is this strange order happens in PriorityQueue in java?](http://stackoverflow.com/questions/12369204/why-is-this-strange-order-happens-in-priorityqueue-in-java) — assylias, Dec 02 '12 at 11:23

assylias · Answer 1 · 2012-12-02T11:19:14.400

9

According to the javadoc for the iterator:

The iterator does not return the elements in any particular order.

However, the first item (head) is guaranteed to be the smallest. So this should print what you expect:

public static void main(String[] args) throws Exception {
    Queue<String> q = new PriorityQueue<String>();
    q.offer("car");
    q.offer("airplane");
    q.offer("bicycle");
    String e = null;
    while ((e = q.poll()) != null) {
        System.out.println(e);
    }
}

If you want iteration to be sorted, you need to use a different structure, for example a TreeSet if you don't have duplicates.

edited Dec 02 '12 at 11:19

answered Dec 02 '12 at 11:13

assylias

321,522
82
660
783

@Lang It is probably not random - I haven't looked at the implementation, but what possibly happens when you insert a new item is that either it is smaller than the head and gets inserted first or, if not, it is put at the tail. That would explain the order you see. – assylias Dec 02 '12 at 11:18
But why I'm always getting that same random order? Something's up with Iterator. – Dec 02 '12 at 11:18
1

(sorry my question ended up after your answer) – Dec 02 '12 at 11:25

Evgeniy Dorofeev · Accepted Answer · 2012-12-02T14:20:35.000

2

PriorityQueue is based on a priority heap. This data structure allows to retrieve the least element very quickly though the elements are not sorted. Adding elements to PriorityQueue is faster than to TreeSet which is tree based. Since the elements are not sorted, the iterator, as API says, "does not return the elements in any particular order".

edited Dec 02 '12 at 14:20

answered Dec 02 '12 at 12:48

Evgeniy Dorofeev

133,369
30
199
275

Queue not ordering naturally

2 Answers2

Linked

Related