wood burning stoves 2.0*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Mystic with PriorityQueue Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCM Java EE 6 Enterprise Architect Exam Guide this week in the OCMJEA forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Mystic with PriorityQueue" Watch "Mystic with PriorityQueue" New topic
Author

Mystic with PriorityQueue

Vadim Vararu
Ranch Hand

Joined: Jan 03, 2009
Posts: 147


and that prints [A,A,V,J]

Where is the logic? It should order it in the natural order A,A,J,V.

Any ideas?


If you think you've done too much, usually it means you've done too few.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18765
    
  40

Vadim Vararu wrote:

and that prints [A,A,V,J]

Where is the logic? It should order it in the natural order A,A,J,V.

Any ideas?


The println() method uses the toString() method -- to get the string to print. Following the JavaDoc, here is the doc for the toString() method.


public String toString()

Returns a string representation of this collection. The string representation consists of a list of the collection's elements in the order they are returned by its iterator, enclosed in square brackets ("[]"). Adjacent elements are separated by the characters ", " (comma and space). Elements are converted to strings as by String.valueOf(Object).


The toString() method uses the iterator, so following the JavaDoc, here is the doc for iterator() method.

public Iterator<E> iterator()

Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.


This is also mentioned at the top of the doc for the priority queue too.

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).


If you want the elements in order, you will have to write the loop and get the elements in the correct order.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Helen Ma
Ranch Hand

Joined: Nov 01, 2011
Posts: 451
Hi, for more information about the priority queue ordering, refer to the SCJP study guide by Mughal and Rasumsen.

Basically, the A A V J are ordered in priority heap structure. It is a binary tree. If the priority queue sort the string items in natural ordering, the root of the tree must be the first sorted item, A. I am not quiet familiar with priority heap structure. You can refer to some college computer science data structure textbook, or google heap sort for more details. But for the exam, I don't think we need to know details about heap sort.
But I guess the heap is like this:
A
A V
J

To transverse the heap, it prints out A A V J, from root , to the first level and second level....

So, priority queue is ordered by natural ordering or comparator specified, but not sorted. So for the exam, don't worry about heap sort as the K&B never talks about it.

But the key thing you need to know for priority queue is poll() or peek(). When it poll , it outputs and remove the items with the highest priority,which is in the root of the heap. Once it is removed, the next priorty item moves up to the root to fill the vacant node.
If A in the root node is polled , the heap looks like this:
A
J V
If A is polled, the heap looks like this:
J
V

In the exam, you only have 2.5 minutes to answer a question, I would suggest you to take a short cut, first sort the items by natural ordering or by the given comparator. Then, you will see which one is removed by the poll().
Correct me if I am wrong.
Helen Ma
Ranch Hand

Joined: Nov 01, 2011
Posts: 451
Let me explain how "JAVA" are added to the heap. Correct me if I am wrong.
First, " J " is added. The heap is
J

Second, "A" is added, the heap is:
J
A
But by natural ordering, A is smaller, so A moves up the path,
A
J

Third, "V" is added, the heap is
A
J V

Last, "A" is added on the second leve, the heap is:
A
J V
A

But A is smaller than its parent node J, so it moves up and swap position with J.
A
A v
J

To express it in a linear order : it is A A V J . The heap is transformed into an array actually and therefore, it prints A A V J.
When you poll, remove A in the root. The second A fills up the root node, and the J moves up and etc.

In general , the root has higher priority , the first level has higher priority than the second level and etc. Unlike binary search tree, left child does not mean it is smaller than the right child. For heap, left child may be bigger than the right child. But the most important thing is we need to make sure the items with higher priority are in the higher level of the tree.




saloni jhanwar
Ranch Hand

Joined: Feb 09, 2012
Posts: 583

Helen Ma wrote:Let me explain how "JAVA" are added to the heap. Correct me if I am wrong.................

I don't believe that because of heap structure, iterator yields AAVJ.I believe that elements are added in priory queue according to comparator provided order or natural order like AAJV but becuaseof Iterator doesn't confirm any ordering that's why it yields AAVJ .


Tell the difficulties that i am difficult.
Dan Drillich
Ranch Hand

Joined: Jul 09, 2001
Posts: 1176
Similar thing at Not able to understand output of the program related to PriorityQueue?.

Regards,
Dan


William Butler Yeats: All life is a preparation for something that probably will never happen. Unless you make it happen.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Mystic with PriorityQueue