Java Natural ordering

Question

I'm trying to use a priorityqueue and I assume the elements are added in the "natural order"..

WHen I print the elements its not in sorted order..I would expect the result- 1,2,3,4

package scratch;
import java.util.*;

public class test {
    public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<String>();
        pq.add("2");
        pq.add("4");
        System.out.println(pq.peek()+" ");
        pq.offer("1");
        pq.add("3");
        System.out.println(pq);
        /*System.out.println(pq.poll() + " ");
        System.out.println(pq);*/
    }

}

OUtput:

2 [1, 3, 2, 4]

`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()).` — nachokk, Sep 04 '13 at 16:23
Possible duplicate of [The built-in iterator for java's PriorityQueue does not traverse the data structure in any particular order. Why?](http://stackoverflow.com/questions/2277430/the-built-in-iterator-for-javas-priorityqueue-does-not-traverse-the-data-struct) — Raedwald, Feb 22 '16 at 14:39

score 4 · Answer 1 · answered Sep 04 '13 at 16:25

The string representation of a PriorityQueue does not reflect anything about the order of elements within it, it is solely based on the iteration order of the queue's iterator() (this is how toString() is defined in AbstractCollection, and PriorityQueue uses this implementation as well). From the linked documentation:

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

nachokk · Answer 2 · 2013-09-04T16:30:41.913

From PriorityQueue

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

And cause you are using toString() that is defined in AbstractCollection and as you see use iterator so order is not guaranteed.

public String toString() {
        Iterator<E> it = iterator();
        if (! it.hasNext())
            return "[]";

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            E e = it.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext())
                return sb.append(']').toString();
            sb.append(',').append(' ');
        }
    }

But this doesn't explain why `toString()` works the way it does. After all, the OP is not using an iterator directly anywhere in his code. — arshajii, Sep 04 '13 at 16:27

score 3 · Accepted Answer · answered Sep 04 '13 at 16:27

In Java, PriorityQueue only guarantees that removing (getting) elements are in particular order. Browsing the internals using the iterator can be of any ordering.

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

And PriorityQueue inherits toString() method from AbstractCollection, which as shown in the source code: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/AbstractCollection.java#AbstractCollection.toString%28%29 uses the iterator to construct the String

public String toString() {
        Iterator<E> i = iterator();
        if (! i.hasNext())
            return "[]";

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            E e = i.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! i.hasNext())
                return sb.append(']').toString();
            sb.append(", ");
        }
    }

So to get data in the sorted order you have to remove them from the container (or sort them with other method):

while (!pq.isEmpty()) System.out.print( pq.poll()+" ");

prints

1 2 3 4

Java Natural ordering

3 Answers3