Is PriorityQueue a ordered and sorted collection?

PriorityQueue is certainly ordered, but is it sorted? Yes it is. However it's not of the type for the sorted collections, such as SortedSet and SortedMap.

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

PriorityQueue 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. A PriorityQueue does not permit null elements. A PriorityQueue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException). When you do not create the PriorityQueue with a Comparator, the elements that you add to the queue must be mutually Comparable (e.g., This means that your element class need to to implement Comparable interface).

The PriorityQueue 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 PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

Only the order as seen by the Queue methods (element(), peek(), poll(), remove()) is guaranteed to reflect the sorted order. The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily.

Therefore, PriorityQueue is a bit outside Java's "standard" sorted collections as defined by SortedSet and SortedMap. For this reason, some people would say that PriorityQueue is ordered but not Sorted.

Printer-friendly version | Mail this to a friend