• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Priority Queue and iterator

 
Greenhorn
Posts: 10
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A short look into the Javadoc for the PriorityQueue answers your question:

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

 
Ranch Hand
Posts: 451
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 451
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
For more information, you can take a look at the post named "Mystic with PriorityQueue" posted on February, 04, 2012.

Correct anything if the answer is wrong in the post thread.
 
Arvind Darwin
Greenhorn
Posts: 10
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Got it! Thanks for the explanation.
 
reply
    Bookmark Topic Watch Topic
  • New Topic