Priority Queue Ordering

[Babugouda patil]

Hi,

As per K&B book PriorityQueue is in sorted by order but I have question here when first I added elements into priorityqueue and printed it worked fine but after adding another element into priorityqueue order got changed and am not able to predict answer:( for this can anyone explain me.

LinkedList worked fine but PriorityQueue is not working

import java.util.*;
class QueueTest 
{
	public static void main(String[] args) 
	{
		Queue<Integer> queue  = new LinkedList<Integer>();
		queue.add(1);
		queue.add(5);
		queue.add(4);
		queue.add(2);
		System.out.println("LikedList Queue before:"+queue);
		queue.add(0);
		System.out.println("LikedList Queue after:"+queue);

		PriorityQueue<Integer> queue1  = new PriorityQueue<Integer>();
		queue1.add(1);
		queue1.add(5);
		queue1.add(4);
		queue1.add(2);
		System.out.println("PriorityQueue Queue before:"+queue1);
		queue1.add(0);
		System.out.println("PriorityQueue Queue after:"+queue1);
		
	}
}

output :
LikedList Queue before:[1, 5, 4, 2]
LikedList Queue after:[1, 5, 4, 2, 0]
PriorityQueue Queue before:[1, 2, 4, 5]
PriorityQueue Queue after:[0, 1, 4, 5, 2]

Please explain me.

[Bhanu Prakash k]

Babugouda,

This link might help you to clarify your question.

-Bhanu.

[Rahul Sudip Bose]

First, thanks to both of you for making me aware of this problem. .I changed the code to get proper output (after some errors in casting....etc). Please let me know if my code can be shorter/better :

/*ANOMALY IN ITERATOR OF PRIORITY QUEUE 
The iterator provided (and used internally) does not traverse the PriorityQueue in its natural order.

*/
    
	import java.util.*;  
    class QueueTest   
    {  
        public static void main(String[] args)   
        {  
            Queue<Integer> queue  = new LinkedList<Integer>();  
            queue.add(1);  
            queue.add(5);  
            queue.add(4);  
            queue.add(2);  
            System.out.println("LikedList Queue before:"+queue);  
            queue.add(0);  
            System.out.println("LikedList Queue after:"+queue);  
      
            PriorityQueue<Integer> queue1  = new PriorityQueue<Integer>();  
            queue1.add(1);  
            queue1.add(5);  
            queue1.add(4);  
            queue1.add(2);  
            System.out.println("PriorityQueue Queue before:"+queue1);  
            queue1.add(0);
			
            System.out.println("PriorityQueue Queue after:"+queue1);  //ANOMALY  !
			
                        //WORKAROUND 
 
			Object[] nos = queue1.toArray();
			Arrays.sort(nos);
			queue1.clear();
			
			for(Object x : nos)
			{
				Integer n = (Integer)x;
				queue1.offer(n);
				
			}
			
			System.out.println("PriorityQueue Queue after:"+queue1); 
			
       }  
		
}

Output :

LikedList Queue before:[1, 5, 4, 2]
LikedList Queue after:[1, 5, 4, 2, 0]
PriorityQueue Queue before:[1, 2, 4, 5]
PriorityQueue Queue after:[0, 1, 4, 5, 2]                     ------>ANOMALY
PriorityQueue Queue after:[0, 1, 2, 4, 5]                     ------>CORRECTION

thanks again !

[Babugouda patil]

Thanks for this short coding Rhul Now i have question if I get this type question in exam what ans i should give According K & B book the PQ is sorted:(
please answer me

[Ikpefua Jacob-Obinyan]

Babugouda patil wrote:

Now i have question if I get this type question in exam what ans i should give According K & B book the PQ is sorted.

Ikpefua wrote:

Hello Babugouda, your question is interesting. Now let us assume you get a question that asks you if PriorityQueue is Sorted, your answer should be YES, this is because elements of a PriorityQueue MUST be mutually comparable meaning that the objects you add to the PriorityQueue MUST implement the Comparable interface. Thit is a FUNDAMENTAL characteristics of Sorted collections.

Lets assume that that you are asked the output of an iteration, your answer should be that it is NOT guaranteed. If you have any doubts you should go to the official java API http://download.oracle.com/javase/6/docs/api/ for more details. I already did that and this is what I discovered:

A.Does NOT permit insertion of non-comparable objects (doing so may result in ClassCastException). Answer to the first question.

B.The Iterator provided in method iterator() is NOT guaranteed to traverse the elements of the priority queue in any particular order. Answer to second question.

Thank you once again for your intelligent question! I have just learnt something new about PriorityQueues!.

[Babugouda patil]

Hi All,

Thanks for the complement

[Francis Zabala]

Sorry... I misread my output.

[Ikpefua Jacob-Obinyan]

Hello Everybody,
I also want to say in addition that in terms of iteration, HashSet behaves in a similar way as in PriorityQueue. It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. OUKC Oracle mock exams specifically has a question that tests your knowledge on the iteration order in HashSet, this means that you are likely to find a similar question in the real exams. So we now know the answer:

iteration order of HashSet and PriorityQueue are NOT guaranteed!.

[Babugouda patil]

Yes Jacob I agree with you. If we get answer from the author it will be good and we can guarantee it.