Ordering in PriorityQueue

[Mohit Jain]

Java documentation for PriorityQueue class and K&B page# 544/545 says - it maintains elements in "natural order" which I believe is sorted order.

I executed following code -
import java.util.*;

public class Static {
public static void main(String args[]){

Queue q = new PriorityQueue();
q.add(new Integer(9));
q.add(new Integer(22));
q.add(new Integer(5));
q.add(new Integer(3));
q.add(new Integer(12));

Iterator it = q.iterator();
while(it.hasNext())
{
System.out.println(it.next());
}
}
}
Output -
3
5
9
22
12

I couldnt understand what kind of ordering is it. Can somebody please help me on this.
Thanks in advance.

[Kelvin Chenhao Lim]

Hi Mohit,

The iterators for Queue collection classes are not guaranteed to return their elements in any particular order. You'll get the correct sorted order only by repeatedly calling the queue's poll() method.

This is a bit non-intuitive because List classes do guarantee that their iterators return elements in the correct order, and LinkedList is both a List and a Queue. But just remember that most collection classes make no guarantees about their iterator order, and this is generally true of Queue as well.
[ November 24, 2007: Message edited by: Kelvin Lim ]

[Mohit Jain]

Hi Kelvin

I understand that. But what exactly it means when they say that "PriorityQueue maintains the elements in natural order"??

Second Question: They say that in PriorityQueue order is generally determined on basis of their "priority". I m curious about who decides this priority and on what basis?

Any help would be greatly appreciated.
[ November 24, 2007: Message edited by: Mohit Jain ]

[Kelvin Chenhao Lim]

"Natural order" means the order given by the object's compareTo() method (for Comparable classes). Note that you can also override the natural ordering by creating the PriorityQueue with a Comparator.

For Integer objects, the natural order is what you'd expect: ascending order of numerical value. So when you poll your queue, it'll return the elements in this order: 3, 5, 9, 12, 22.

The term "priority queue" is a bit of a Computer Science tradition, since this sort of abstract data structure is typically used for things like retrieving the next highest-priority job to perform, or selecting the operation/item with the next lowest cost. Don't get too hung up on the terminology here. You can use a priority queue for lots of applications that have nothing to do with priority per se.

(P.S.: priority queues are traditionally implemented using binary heap arrays, so PriorityQueue's iterator is most likely returning its elements in the order stored in the array. In fact, the "3 5 9 22 12" output you reported is exactly consistent with a binary heap, given your insertion order. But that's an implementation detail that you don't need to know, and which you also cannot assume will be true across implementations and Java versions.)
[ November 24, 2007: Message edited by: Kelvin Lim ]