# SCJP Priority Queue Please help

ali kamran

Greenhorn

Posts: 29

posted 3 years ago

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....

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

posted 3 years ago

Running -

prints -

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

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

Regards,

Dan

- 1

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.

posted 3 years ago

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

specifically read the post by Ankit Garg

Brian Evans

Greenhorn

Posts: 7

Helen Ma

Ranch Hand

Posts: 451

ali kamran

Greenhorn

Posts: 29

Helen Ma

Ranch Hand

Posts: 451

posted 3 years ago

- 1

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.

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.

posted 3 years ago

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

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.

- 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

Posts: 29

posted 3 years ago

Thank you sooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo much .Much appreciated yeas that is how the elements came out.Thanks again

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