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

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.

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"

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

posted

0

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