aspose file tools*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Isn't PriorityQueue a sorted collection? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Isn Watch "Isn New topic
Author

Isn't PriorityQueue a sorted collection?

Bing Qiao
Greenhorn

Joined: Oct 24, 2006
Posts: 21
In the SCJP book, on page 543, it says "The ThreeSet is one of two sorted collections (the other being TreeMap)."

Then on page 545, table 7-2 Collection Interface Concrete Implementation Classes: PriorityQueue is marked as "Sorted".

Isn't PriorityQueue a sorted collection?

Thanks!
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

Yes, PriorityQueue is a Collection (it implements the Collection interface) and it is ordered. From the API documentation...
This queue orders elements according to an order specified at construction time, which is specified either according to their natural order (see Comparable), or according to a Comparator, depending on which constructor is used.

Note that PriorityQueue was introduced with version 1.5. Which version is your book for?


"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
sscce.org
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[Bing]: Isn't PriorityQueue a sorted collection?

[marc]: Yes, PriorityQueue is a Collection (it implements the Collection interface) and it is ordered.


But ordered and sorted are not the same thing. All sorted collections are also ordered, but not all ordered collections are sorted. A List for example is always ordered - its elements have definite positions - but it isn't sorted unless you sort it somehow (e.g. with Collections.sort()).

PriorityQueue is certainly ordered, but is it sorted? Yes it is. However it's not a member of the two APIs for sorted collection-like things, namely SortedSet and SortedMap. And the iteration order of PriorityQueue isn't sorted - only the order as seen by the Queue methods (element(), peek(), poll(), remove()) is guaranteed to reflect the sorted order. So PriorityQueue is a bit outside Java's "standard" sorted collections as defined by SortedSet and SortedMap. Perhaps that's the reason for the apparent discrepancy on how K & B describes it. I would say that PriorityQueue is sorted but not Sorted.
[ October 24, 2006: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, Twister
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

Originally posted by Jim Yingst:
...ordered and sorted are not the same thing. All sorted collections are also ordered, but not all ordered collections are sorted...

...I would say that PriorityQueue is sorted but not Sorted.

Good point! I should have been more clear. Thanks for clarifying.
[ October 24, 2006: Message edited by: marc weber ]
Bing Qiao
Greenhorn

Joined: Oct 24, 2006
Posts: 21
Thanks you both!

Still a bit confused. But maybe it doesn't really matter for the exam since it didn't deserve a clarification in the book.
[ October 25, 2006: Message edited by: Bing Qiao ]
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

Originally posted by Bing Qiao:
... Still a bit confused...

Good. Here's my chance to be more clear.

SortedSet and SortedMap are interfaces that guarantee a sorted iteration order of elements. (In a SortedMap, sorting is applied to the keys.)

TreeSet is a class that implements the SortedSet interface, and TreeMap is a class that implements the SortedMap interface. So by their "contract" with the interfaces, TreeSet and TreeMap are guaranteed to be sorted.

PriorityQueue is a Collection that does not implement SortedSet or SortedMap. In fact, the "Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order."

But at the same time, PriorityQueue provides sorted functionality in its implementation of Queue methods: element, peek, poll, and remove. (Note that Queue is an interface implemented by PriorityQueue.) These methods each work with the "head" of the queue, as determined by Comparable or Comparator.

So when Jim suggested (with a ) that "PriorityQueue is sorted but not Sorted," I believe he is pointing out that PriorityQueue is not Sorted (with an uppercase 'S' implying a type, SortedSet or SortedMap), but it does have some sorted (lowercase 's') functionality.

(Right?)
[ October 25, 2006: Message edited by: marc weber ]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Isn't PriorityQueue a sorted collection?