This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes SCJP Priority Queue Please help Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "SCJP Priority Queue Please help" Watch "SCJP Priority Queue Please help" New topic
Author

SCJP Priority Queue Please help

ali kamran
Greenhorn

Joined: Apr 25, 2010
Posts: 29

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

Joined: Jul 09, 2001
Posts: 1167
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


William Butler Yeats: All life is a preparation for something that probably will never happen. Unless you make it happen.
gurpeet singh
Ranch Hand

Joined: Apr 04, 2012
Posts: 924
    
    1

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

Joined: May 08, 2012
Posts: 7
Ali,

I attempted to answer your question in the linked thread above.
Helen Ma
Ranch Hand

Joined: Nov 01, 2011
Posts: 451
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

Joined: Apr 25, 2010
Posts: 29


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

Joined: Nov 01, 2011
Posts: 451
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

Joined: Apr 04, 2012
Posts: 924
    
    1

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

Joined: Apr 25, 2010
Posts: 29
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
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: SCJP Priority Queue Please help
 
Similar Threads
Offer VS add
Print contents of PriorityQueue not working
PriorityQueue()
Natural Ordering with PriorityQue and String representations of integers
SCJP CH 7 Q9 PQ