• 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
  • Tim Cooke
  • Devaka Cooray
  • Ron McLeod
  • Jeanne Boyarsky
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Carey Brown
  • Tim Holloway
Bartenders:
  • Martijn Verburg
  • Frits Walraven
  • Himai Minh

Problem regarding a PriorityQueue concept

 
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Table on page 545 in K&B's book for scjp lists that PriorityQueue is sorted by to-do order.

and while reading the book "the java programming language" i found this description:

"The other Queue implementation is PriorityQueue, an unbounded queue, based on a priority heap. The head of the queue is the smallest element in it, where smallest is determined either by the elements' natural order or by a supplied comparator. A PriorityQueue is not a sorted queue in the general senseyou can't pass it to a method expecting a sorted collection because the iterator returned by iterator is not guaranteed to traverse the elements in priority order; rather it guarantees that removing elements from the queue occurs in a given order. The iterator can traverse the elements in any order. If you need ordered traversal you could extract the elements to an array and then sort the array."

bit confused about these, i think i'm not getting the right meaning out of this paragraph above. So is PriorityQueue sorted or is it not?
please help resolve this confusion.

Thank you.
 
Ranch Hand
Posts: 1183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The concept is that a PriorityQueue is not necessarily made for iteration. That's why it does not guarantee any order upon traversing the queue. What it practically is made for is adding elements (offer) and removing them (poll).

The order in which they get removed is determined by either the natural order or by a Comparator.

Think about a HashSet for instance. you cannot say set.remove() or set.poll() without telling the set what to remove. That's the difference.
 
rushikesh sawant
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
thanks for reply.
so does it mean that elements in PriorityQueue are not stored in a sorted manner of any kind? and its just the order in which they get removed is determined by either the natural order or by a comparator.
 
Sheriff
Posts: 9697
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

so does it mean that elements in PriorityQueue are not stored in a sorted manner of any kind? and its just the order in which they get removed is determined by either the natural order or by a comparator.


Yes the elements are not stored in a sorted order in the queue and the sorting comes into play when you call poll or peek methods...
 
rushikesh sawant
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for clarification.
 
The fastest and most reliable components of any system are those that are not there. Tiny ad:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic