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.

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

posted

0

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.

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 .