Note able to understand output of the program related to PriorityQueue?

[gurpeet singh]

Please consider the following program

import java.util.PriorityQueue;

class TestSort1 {

    public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<String>();
        pq.add("2");
        pq.add("4");
        pq.add("7");
        pq.add("9");
        pq.add("12");
        for (String s : pq) {                                   //the stack trace shows error at here
            System.out.println(pq.poll());
        }
    }
}

when i run this it gives me the following error :

Exception in thread "main" java.util.ConcurrentModificationException
at java.util.PriorityQueue$Itr.next(PriorityQueue.java:464)
at javaapplication10.TestSort1.main(JavaApplication10.java:17)
Java Result: 1

the second part to my question is that if i modify the code and use normal for loop to see how poll() method works, then it gives me output as follows no matter how many times i run ? please explain?

12
2
4
7
9

[Henry Wong]

gurpeet singh wrote:Please consider the following program

import java.util.PriorityQueue;

class TestSort1 {

    public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<String>();
        pq.add("2");
        pq.add("4");
        pq.add("7");
        pq.add("9");
        pq.add("12");
        for (String s : pq) {                                   //the stack trace shows error at here
            System.out.println(pq.poll());
        }
    }
}

when i run this it gives me the following error :

Exception in thread "main" java.util.ConcurrentModificationException
at java.util.PriorityQueue$Itr.next(PriorityQueue.java:464)
at javaapplication10.TestSort1.main(JavaApplication10.java:17)
Java Result: 1

the second part to my question is that if i modify the code and use normal for loop to see how poll() method works, then it gives me output as follows no matter how many times i run ? please explain?

12
2
4
7
9

I am assuming that your alternate loop doesn't use the iterator? ... The Java foreach loop uses the iterator for iterable collections, and with the exception of a few collections, most do not allow the changing of the collection (add or remove of elements) during iteration. You get the concurrent modification exception when you do that.

Henry

[gurpeet singh]

thanks henry but i'm still confused. can you explain a bit. secondly when i use normal for loop , it always prints the output as:
12
2
4
7
9

I know that priority queue are naturally ordered or according to the comparator , depending on whichever constructor is used to construct it. i also know that the iterator returns elements in any order, but if we use poll() method, it will always remove head of the queue accroding to the natural ordering. so in case of say for numbers the ordering will be from low to high and in case of strings it will be alphabetical order. but in this case since the strings are numbers how the natural ordering is decided by the poll method , or is there any natural ordering at all ? please explain

[Ankit Garg]

gurpeet singh wrote:secondly when i use normal for loop

Can you show us the code of this normal for loop? If you see the output, the output, the elements are alphabetically ordered. "12" should come before "2" in alphabetical ordering. "1290" would come before "72" in alphabetical ordering as the comparison would be done on each alphabet one-by-one and "1" would be smaller than "7"...

[gurpeet singh]

    import java.util.PriorityQueue;  
      
    class TestSort1 {  
      
        public static void main(String[] args) {  
            PriorityQueue<String> pq = new PriorityQueue<String>();  
            pq.add("2");  
            pq.add("4");  
            pq.add("7");  
            pq.add("9");  
            pq.add("12");  
            for (int i=0;i<5) {                                   //the stack trace shows error at here  
                System.out.println(pq.poll());  
            }  
        }  
    }  

the for loop i used was simple for loop. but i would like to know how the poll method retrieves the head of the queue. ??

[Henry Wong]

gurpeet singh wrote:

    import java.util.PriorityQueue;  
      
    class TestSort1 {  
      
        public static void main(String[] args) {  
            PriorityQueue<String> pq = new PriorityQueue<String>();  
            pq.add("2");  
            pq.add("4");  
            pq.add("7");  
            pq.add("9");  
            pq.add("12");  
            for (int i=0;i<5) {                                   //the stack trace shows error at here  
                System.out.println(pq.poll());  
            }  
        }  
    }  

the for loop i used was simple for loop. but i would like to know how the poll method retrieves the head of the queue. ??

As suspected, you didn't use the iterator. The foreach loop does use the iterator -- and for most collections, you can't use the iterator *and* change the collection at the same time. And if you do, you see the exception that you saw.

Henry

[gurpeet singh]

okay i got the reason for Concurrent modification exception. but i would like to know what happens when i use normal for loop. how would you explain the output then ?

[Henry Wong]

gurpeet singh wrote:okay i got the reason for Concurrent modification exception. but i would like to know what happens when i use normal for loop. how would you explain the output then ?

Reread the response by Ankit Garg.

Henry

[David Means]

What you're trying to do is iterate over the PriorityQueue. I do not believe you can do that on the raw PriorityQueue object (please correct if I'm wrong), rather you must either use an Iterator or convert it to an array.

Convert to an array:

Object[] pqs = pq.toArray();
for (Object o : pqs)
{
    System.out.println(pq.poll());
}

Obtain an Iterator:

Iterator<String> pi = pq.iterator();
while (pi.hasNext())
{
    System.out.println(pi.next());
}

In both cases, you're presented with the desired list.
Here's the new code (with one change):

class TestSort1
{

    @SuppressWarnings("unused")
    public static void main(String[] args)
    {
        int selection = 1;
        PriorityQueue<String> pq = new PriorityQueue<String>();
        pq.add("2");
        pq.add("4");
        pq.add("7");
        pq.add("9");
        pq.add("12");

        if (selection == 1)
        {
            Object[] pqs = pq.toArray();
            for (Object o : pqs)
            {
                System.out.println("Object Loop: " + pq.poll());
            }
            System.out.println("pq has " + pq.size() + " elements.");
        }
        else
        {
            Iterator<String> pi = pq.iterator();
            while (pi.hasNext())
            {
                System.out.println("Iterator Loop: " + pq.poll());
            }
            System.out.println("pq has " + pq.size() + " elements.");
        }
    }
}

[ali kamran]

Ankit Garg wrote:

gurpeet singh wrote:secondly when i use normal for loop

Can you show us the code of this normal for loop? If you see the output, the output, the elements are alphabetically ordered. "12" should come before "2" in alphabetical ordering. "1290" would come before "72" in alphabetical ordering as the comparison would be done on each alphabet one-by-one and "1" would be smaller than "7"...

hey ankit may you please explain me the order of my code..

Hello all,
Have a question with regards to Queue,Priority queue.Question below from K&B scjp book Ch 7 Q9
<code>
9. Given the proper import statement(s), and
13. PriorityQueue<String> pq = new PriorityQueue<String>();
14. pq.add("2");
15. pq.add("4");
16. System.out.print(pq.peek() + " ");
17. pq.offer("1");
18. pq.add("3");
19. pq.remove("1");
20. System.out.print(pq.poll() + " ");
21. if(pq.remove("2")) System.out.print(pq.poll() + " ");
22. System.out.println(pq.poll() + " " + pq.peek());

</code>
What is the result?
A. 2 2 3 3
B. 2 2 3 4
C. 4 3 3 4
D. 2 2 3 3 3
E. 4 3 3 3 3
F. 2 2 3 3 4
G. Compilation fails
H. An exception is thrown at runtime

What I Expected:
Now I would expect it adds 2-->then 4-->then peek so display 2 -->then add 1 and 3 so now we have [2,4,1,3] --> remove 1 -->poll so remove 2 now [4,3] -->if fails -->then poll and peek so display 4 and 3.Thus answer should be 2 2 4 3

What It is:
2 2 3 4.

What I did:
When I popped it in code I see 3 ahead of 4


<code>
package TEST2;

import java.util.PriorityQueue;
import java.util.TreeMap;

public class Q9 {
public static void main(String args[])
{
TreeMap<String,String> mymap= new TreeMap<String,String>();

PriorityQueue<String> pq = new PriorityQueue<String>();
pq.add("2");
pq.add("4");
System.out.println("pq is"+pq);
System.out.println(pq.peek() + " ");
pq.offer("1");
pq.add("3");
System.out.println("pq is"+pq);
pq.remove("1");
System.out.println("3rd pq is"+pq);
System.out.println(pq.poll() + " ");
if(pq.remove("2"))
System.out.println(pq.poll() + " ");
System.out.println(pq.poll() + " " + pq.peek());


}


}

</code>

What the issue is:
In the syso why do I see 1 and 3 inserted ahead of 2 and 4 ?
Somebody please have the patience to explain me .Much appreciated....

[Brian Evans]

ali kamran wrote:
What the issue is:
In the syso why do I see 1 and 3 inserted ahead of 2 and 4 ?
Somebody please have the patience to explain me .Much appreciated....

If a Priority Queue is created without a specified comparator, the pq will use natural ordering as specified by the Collection class. For strings, this means lexicographic ordering.

Since this is a priority queue, all inserted elements will be placed in the queue based on their given "priority, which in this case is their lexicographic ordering.

In your example, the PQ looks like this:

Empty Queue: []
Add("2") => [2]
Add("4") => [2,4]

PRINT(PEEK) => PRINT(2)

Offer("1") => [1,2,4]
Add("3") => [1,2,3,4]
Remove("1") => [2,3,4]

PRINT(POLL) => PRINT(2) .... *Note that the pq is now [3,4]*
*If is ignored since there is no "2"*
PRINT(POLL + PEEK) => PRINT(3) *Note that the pq is now [4]* + PRINT(4)

The final output is 2 2 3 4. The mistake you were making earlier, is that the structure given is a priority queue, not a queue.

[Dan Drillich]

Good Day,

If we look at -

import java.util.PriorityQueue; 
import java.util.TreeMap; 

public class Q9 { 

public static void main(String args[]) 
{ 

PriorityQueue<String> pq = new PriorityQueue<String>(); 


pq.add("3");
pq.add("2"); 
pq.add("4"); 
pq.add("1");
  
System.out.println("pq is"+pq); 
 

} 


} 

It returns -

pq is[1, 2, 4, 3]

Why is it?

Regards,
Dan

[Brian Evans]

Dan Drillich wrote:

Why is it?

Regards,
Dan

If you look at the PriorityQueue API, when printing out the PQ using a system.out call, only the head is guaranteed to be printed accurately. All of the other values in the queue are not guaranteed to be printed correctly. So, whenever you do a poll(), remove(), or peek(), the output will be correct. If you want to see the actual ordering of your PQ, try this code:

while(!pq.isEmpty()) {
   System.out.println(pq.poll() + " ");
}

[Dan Drillich]

Thank you Brian - this makes perfect sense.

Regards,
Dan

[Brian Evans]

Dan Drillich wrote:Thank you Brian - this makes perfect sense.

Regards,
Dan

No Problem Dan, I spent too many hours last night figuring this out