Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

SCJP Priority Queue Please help

 
ali kamran
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Posts: 12
posted Today 1:29:55 AM 0
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....
 
Dan Drillich
Ranch Hand
Posts: 1183
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In the syso why do I see 1 and 3 inserted ahead of 2 and 4 ?


Running -



prints -




which makes sense based on Class PriorityQueue<E> that says -

The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.


But I can't understand what's going on with your example.

Regards,
Dan

 
gurpeet singh
Ranch Hand
Posts: 924
1
Fedora Java Netbeans IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
this will help http://www.coderanch.com/t/574329/java-programmer-SCJP/certification/Note-able-understand-output-program

specifically read the post by Ankit Garg
 
Brian Evans
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ali,

I attempted to answer your question in the linked thread above.
 
Helen Ma
Ranch Hand
Posts: 451
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, Ali.
Google heap sort or read some data structure books about heap sort. Priority queue implements heap sort to sort data.
 
ali kamran
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


But I can't understand what's going on with your example.


That is what needs to be figured.Thanks though
 
Helen Ma
Ranch Hand
Posts: 451
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Suppose you want to add string "2","4" ,"1" , "3" in this order to the priority queue, which implements heap sort.
1. The heap looks like this:


2. Add 4 and the heap looks like this:


3. Add 1, but 1 is small than 2 , so
3.1 1 is added as the right child of 2


3.2 1 moves up on the branch, like this:

4. Add 3 , the heap will be:
4.1 insert 3 to the next level


4.2 move 3 up as it is less than 4


Heap sort can be represented in an array. If so, the zeroth element is 1, first element is 3 , second element is 2 and forth element is 4.

Please verify this.
 
gurpeet singh
Ranch Hand
Posts: 924
1
Fedora Java Netbeans IDE
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Helen Ma wrote:Suppose you want to add string "2","4" ,"1" , "3" in this order to the priority queue, which implements heap sort.
1. The heap looks like this:


2. Add 4 and the heap looks like this:


3. Add 1, but 1 is small than 2 , so
3.1 1 is added as the right child of 2


3.2 1 moves up on the branch, like this:

4. Add 3 , the heap will be:
4.1 insert 3 to the next level


4.2 move 3 up as it is less than 4


Heap sort can be represented in an array. If so, the zeroth element is 1, first element is 3 , second element is 2 and forth element is 4.

Please verify this.


zeroth element is 1
first element is 2
second element is 3
third element is 4

i do not know about the heap sort. but from the javadocs says that
"The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements"


also the link to a related thread which i posted above explains the reason of the output. i'm reposting it below
his will help http://www.coderanch.com/t/574329/java-programmer-...able-understand-output-program

specifically read the post by Ankit Garg


i have forgotten about algorithms and data structures helen, maybe you are doing heap sort wrongly. also i have somewhere read that collection classes uses TIM SORT. which is modified version of heap sort or some other sorting algorithm.
 
ali kamran
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Helen Ma wrote:Suppose you want to add string "2","4" ,"1" , "3" in this order to the priority queue, which implements heap sort.
1. The heap looks like this:


2. Add 4 and the heap looks like this:


3. Add 1, but 1 is small than 2 , so
3.1 1 is added as the right child of 2


3.2 1 moves up on the branch, like this:

4. Add 3 , the heap will be:
4.1 insert 3 to the next level


4.2 move 3 up as it is less than 4


Heap sort can be represented in an array. If so, the zeroth element is 1, first element is 3 , second element is 2 and forth element is 4.

Please verify this.



Thank you sooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo much .Much appreciated yeas that is how the elements came out.Thanks again
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic