Java : PriorityQueue queue results and natural ordering

Question

I know, queue follow FIFO(First in first out) order, but I am not sure why the following output appears with below java sample program

JAVA Sample

  public static void main(String args[]) {
            Queue<String> q = new PriorityQueue<String>();
            q.add("3");
            q.add("1");
            q.add("2");

            Iterator<String> itr = q.iterator();
            while (itr.hasNext()) {
                System.out.println(itr.next() + "    ");
            }
}

OUTPUT :

1    
3    
2

As per Java doc of java.util.PriorityQueue.PriorityQueue()

Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.

Q1) Could any body please explain why the output is 1 3 2 and how the natural order works here.
Q2) I have checked about natural ordering and its related to the Comparable/Comparor but doesn't they are for Sorting(Ascending/Descending) Order only??

Sorry! The initial sample was with LinkedList.Now updated the Java sample with PriorityQueue. — Arun Kumar
– Arun Kumar, Commented Jun 18, 2014 at 7:32

Christoph Schubert · Accepted Answer · 2014-06-18 07:33:22Z

4

The PriorityQueue in Java is a datastructure, that sorts the elements it contains. Excerpt from the Javadoc:

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.

The Problem with the unordered output comes from the iterator implementation. Another excerpt, this time from the iterator() method:

Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.

So you don't java a fixed order with the iterator. If you use the poll() method in a loop you would get all given elements in ascending order.

If you are looking for a Queue in the FIFO-sense you may have a look at the LinkedList and only use the addFirst() and getLast() methods.

answered Jun 18, 2014 at 7:33

Christoph Schubert

1,1241 gold badge9 silver badges16 bronze badges

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

6 Comments

Arun Kumar Over a year ago

Little Weird! The Iterator returns the same order while traversing an ArrayList but for PriorityQueue it doesn't :(

Christoph Schubert Over a year ago

Yep, very unintuitive. Another hint from the JavaDoc: You could use Arrays.sort(q.toArray()) to have an ordered Array with the elements.

Arun Kumar Over a year ago

Just to Update here that even if you used q.toArray() that will return Object[] with natural order. So no need of extra Arrays.sort method here.

Christoph Schubert Over a year ago

Guaranteed? The JavaDoc states Returns an array containing all of the elements in this queue. The elements are in no particular order. Maybe your values had the right order per "accident"?

Arun Kumar Over a year ago

Yes! I just performed following test and traverse the Object array and its returning the elements in sorted manner Object[] ob=(Object[]) q.toArray(); for(int i=0;i<q.size();i++) System.out.println(ob[i]);

|

Collectives™ on Stack Overflow

Java : PriorityQueue queue results and natural ordering

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related