• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

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

 
gurpeet singh
Ranch Hand
Posts: 924
1
Fedora Java Netbeans IDE
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please consider the following program




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
author
Marshal
Pie
Posts: 20836
75
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
gurpeet singh wrote:Please consider the following program




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
Ranch Hand
Posts: 924
1
Fedora Java Netbeans IDE
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 9497
22
Android Google Web Toolkit Hibernate IntelliJ IDE Java Spring
  • 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 924
1
Fedora Java Netbeans IDE
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


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
author
Marshal
Pie
Posts: 20836
75
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
gurpeet singh wrote:

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
Ranch Hand
Posts: 924
1
Fedora Java Netbeans IDE
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
author
Marshal
Pie
Posts: 20836
75
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 1
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:



Obtain an Iterator:



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

 
ali kamran
Greenhorn
Posts: 29
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 7
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 1183
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Good Day,

If we look at -



It returns -



Why is it?

Regards,
Dan
 
Brian Evans
Greenhorn
Posts: 7
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:

 
Dan Drillich
Ranch Hand
Posts: 1183
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you Brian - this makes perfect sense.

Regards,
Dan
 
Brian Evans
Greenhorn
Posts: 7
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic