Doubt in priority Queue implementation

[vijay makam]

As far as my understanding goes after reading some java books I think If we are not using a comparator for our priority queue then the insertion will FIFO. But after executing the below program I am getting a different one.

public class PriorityQueueTest {
public static void main(String args[]){
    PriorityQueue<String> pq=new PriorityQueue<String>();
    pq.add("banana");
    pq.add("peach");
    pq.add("apple");
    pq.add("orange");
    pq.add("plum");
    
    for (String s: pq) 
        System.out.println("pq's element:"+s);
    
    System.out.println("POLLING..."+pq.poll()+"  PEEK�"+pq.peek());
    for (String s: pq) 
        System.out.println("pq's element:"+s);
    System.out.println("POLLING..."+pq.poll()+" PEEK�"+pq.peek());
    for (String s: pq) 
        System.out.println("pq's element:"+s);
    System.out.println("POLLING..."+pq.poll()+" PEEK�"+pq.peek());
    for (String s: pq) 
        System.out.println("pq's element:"+s);
}
}

Please let me know what is happening in the above piece of code.

Thanks in advance
[edit]Alter spacing to avoid smilies, and add code tags. CR[/edit]
[ September 30, 2008: Message edited by: Campbell Ritchie ]

[Piet Verdriet]

Originally posted by vijay makam:
As far as my understanding goes after reading some java books I think If we are not using a comparator for our priority queue then the insertion will FIFO. ...

No, that is not correct. If no Comparator is provided, the elements get sorted according their natural order. Strings are compared lexicographically. So "B" comes after "A" but "B" comes before "C": adding "C", "A" and "B" will result in the PQ=["A","B","C"].

HTH

[Henry Wong]

And here is the relevant paragraph in the JavaDoc...

This queue orders elements according to an order specified at construction time, which is specified either according to their natural order (see Comparable), or according to a Comparator, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).

Henry

[vijay makam]

Hi Piet,

Thanks for your reply. But that doesn't solve my confusion.
The output I am getting is neither in the insertion order nor in the natural order.
Here's a snapshot of the partial output (after the first for-each loop).
pq's element: apple
pq's element: orange
pq's element: banana
pq's element: peach
pq's element: plum

[Piet Verdriet]

Hi, run this code to see how PQ internally orders it's elements (and when!):

while(!pq.isEmpty()) {
  System.out.println("PQ before poll() : "+pq);
  System.out.println("poll() -> "+pq.poll());
  System.out.println("PQ after poll()  : "+pq+"\n");
}

To quote the API doc for PQ:

"The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray())"

http://java.sun.com/j2se/1.5.0/docs/api/java/util/PriorityQueue.html
[ October 01, 2008: Message edited by: Piet Verdriet ]