This week's book giveaway is in the OCAJP 8 forum.We're giving away four copies of OCA Java SE 8 Programmer I Study Guide and have Edward Finegan & Robert Liguori on-line!See this thread for details.
Big Moose Saloon
 Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies Register / Login Win a copy of OCA Java SE 8 Programmer I Study Guide this week in the OCAJP 8 forum!

# Priority Queue and iterator

Arvind Darwin
Greenhorn

Joined: Mar 05, 2012
Posts: 10

So I was playing with priority queue. Here is the code (its loosely based on K&B example).

The output is:

Queue created with Descending priority
----------------------------------------
Highest priority: [Name:10]

Iterator
[Name:10][Name:9][Name:7][Name:5][Name:2][Name:3][Name:4][Name:1]

Poll
[Name:10][Name:9][Name:7][Name:5][Name:4][Name:3][Name:2][Name:1]

Queue created with Ascending priority comparator
--------------------------------------------------
Highest priority: [Name:1]

Iterator
[Name:1][Name:2][Name:3][Name:7][Name:5][Name:9][Name:4][Name:10]

Poll
[Name:1][Name:2][Name:3][Name:4][Name:5][Name:7][Name:9][Name:10]

My Question is:

When I use iterator to print values it does not print in order of priority, but when I poll() it follows the priority order.

Why? Can someone please explain this behavior? Iterator does not use comparable or comparator interface?

Thanks.
Norbert Muench
Greenhorn

Joined: Mar 09, 2012
Posts: 19
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()).
Helen Ma
Ranch Hand

Joined: Nov 01, 2011
Posts: 451
The items that are put in a priority queue are sorted by heap sort algorithm. Heap sort is to put items in a binary tree data structure.
The item with the highest priority is put at the root of the tree. The two children has lower priority than the root and so on.
So, when you poll an item, you remove the item in the root of the tree. One of its children move up to the root and so on.
Helen Ma
Ranch Hand

Joined: Nov 01, 2011
Posts: 451
For more information, you can take a look at the post named "Mystic with PriorityQueue" posted on February, 04, 2012.