Win a copy of The Java Performance Companion this week in the Performance forum!

PriorityQueue

Alexsandra Carvalho
Ranch Hand
Posts: 75
Hi,

Why in this code, the result is not [1,2,3] instead of [1,3,2]?

Thirumalai Muthu
Ranch Hand
Posts: 75
Hi Can anyone Please answer to the above question?.Since this priority queue holds Integers and its been ordered in natural order,the output should be[1,2,3] but instead the output is [1,3,2]?

Alexsandra Carvalho
Ranch Hand
Posts: 75
Maybe is because ProrityQueue does not keep the collection sorted, but, when we retrieve the elements, then these elements are retrieve sorted??

Mateus Brum
Greenhorn
Posts: 18
And maybe the first element is always sorted to avoid a overhead when we manipulate it for first time (peek,remove,pool and element) always get the first element.

Ranch Hand
Posts: 339
Hi
I think you are wrong Mr.Mateus Brum .

The original question was:---

Why in this code, the result is not [1,2,3] instead of [1,3,2]?

code:
--------------------------------------------------------------------------------

Queue<Integer> queue= new PriorityQueue<Integer>(); queue.offer(3)
;queue.offer(2);
queue.offer(1);
System.out.println(queue);

You are saying that first element is considered sorted.Then according to you answer should be 15234 for below question but answer is 1245.

Queue<Integer> queue= new PriorityQueue<Integer>();
queue.offer(5);
queue.offer(4);
//queue.offer(3);
queue.offer(2);
queue.offer(1);
System.out.println(queue);

Please anybodoy solve the original problem that is top-most.Why the output is not 123 .
[ January 06, 2008: Message edited by: pradeep singh ]

Thirumalai Muthu
Ranch Hand
Posts: 75
Hi can anyone please give answer to the above question. Why is the output [1,3,2] where we are expecting it as [1,2,3]. Thanks.
[ January 07, 2008: Message edited by: Thirumalai Muthu ]

Nitesh Kant
Bartender
Posts: 1638
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())

The toString() method that is used when you print an Object using System.out.println or any print method, uses the iterator returned by the PriorityQueue. Since, the iterator does not guarantee an order consistent with the Comparable so the output is not what you would otherwise expect.

Ranch Hand
Posts: 339
Hi to all
I am not satisfied with Nitesh Kant solution because PriorityQueue orders its elements according to natural order i.e. 1 comes before 2 then 3... unless and untill we do not provide any ordering using Comparator.

And hence in this question we are not using Comparator .So ordering should be in natural order.

So i think(my personel view,may be i am wrong ) solution provide for above problem by Nitesh Kant is wrong.

Nitesh Kant
Bartender
Posts: 1638
Hi to all
I am not satisfied with Nitesh Kant solution because PriorityQueue orders its elements according to natural order i.e. 1 comes before 2 then 3... unless and untill we do not provide any ordering using Comparator.

And hence in this question we are not using Comparator .So ordering should be in natural order.

So i think(my personel view,may be i am wrong ) solution provide for above problem by Nitesh Kant is wrong.

Could you please let me know as to what you found was wrong in the explanation. I am sure open to anything i missed.
[ January 07, 2008: Message edited by: Nitesh Kant ]

Deepak Jain
Ranch Hand
Posts: 637

The answer is bang on target. When System.out.println(queue) is invoked, the println() method simply invokes queue.toString(); And this invokes toString() of AbstractCollection. Because PriorityQueue extends AbstractQueue and AbstractQueue extends AbstractCollection.

AbstractCollection.toString() :"Returns a string representation of this collection. The string representation consists of a list of the collection's elements in the order they are returned by its iterator"

AbstractCollection.toString() method invokes iterator(), this method is defined in PriorityQueue and the java doc clearly states that the elements returned by iterator are not in any order. "Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order."

Hope this clears