This week's book giveaway is in the Design forum.
We're giving away four copies of DevOps: A Software Architect's Perspective and have Len Bass, Ingo Weber & Liming Zhu on-line!
See this thread for details.
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Ordering in PriorityQueue Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

Win a copy of DevOps: A Software Architect's Perspective this week in the Design forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Ordering in PriorityQueue" Watch "Ordering in PriorityQueue" New topic

Ordering in PriorityQueue

Mohit Jain
Ranch Hand

Joined: Jun 04, 2007
Posts: 74
Java documentation for PriorityQueue class and K&B page# 544/545 says - it maintains elements in "natural order" which I believe is sorted order.

I executed following code -
import java.util.*;

public class Static {
public static void main(String args[]){

Queue q = new PriorityQueue();
q.add(new Integer(9));
q.add(new Integer(22));
q.add(new Integer(5));
q.add(new Integer(3));
q.add(new Integer(12));

Iterator it = q.iterator();
Output -

I couldnt understand what kind of ordering is it. Can somebody please help me on this.
Thanks in advance.

SCJP 5.0, SCWCD in progress
Kelvin Chenhao Lim
Ranch Hand

Joined: Oct 20, 2007
Posts: 513
Hi Mohit,

The iterators for Queue collection classes are not guaranteed to return their elements in any particular order. You'll get the correct sorted order only by repeatedly calling the queue's poll() method.

This is a bit non-intuitive because List classes do guarantee that their iterators return elements in the correct order, and LinkedList is both a List and a Queue. But just remember that most collection classes make no guarantees about their iterator order, and this is generally true of Queue as well.
[ November 24, 2007: Message edited by: Kelvin Lim ]

SCJP 5.0
Mohit Jain
Ranch Hand

Joined: Jun 04, 2007
Posts: 74
Hi Kelvin

I understand that. But what exactly it means when they say that "PriorityQueue maintains the elements in natural order"??

Second Question: They say that in PriorityQueue order is generally determined on basis of their "priority". I m curious about who decides this priority and on what basis?

Any help would be greatly appreciated.
[ November 24, 2007: Message edited by: Mohit Jain ]
Kelvin Chenhao Lim
Ranch Hand

Joined: Oct 20, 2007
Posts: 513
"Natural order" means the order given by the object's compareTo() method (for Comparable classes). Note that you can also override the natural ordering by creating the PriorityQueue with a Comparator.

For Integer objects, the natural order is what you'd expect: ascending order of numerical value. So when you poll your queue, it'll return the elements in this order: 3, 5, 9, 12, 22.

The term "priority queue" is a bit of a Computer Science tradition, since this sort of abstract data structure is typically used for things like retrieving the next highest-priority job to perform, or selecting the operation/item with the next lowest cost. Don't get too hung up on the terminology here. You can use a priority queue for lots of applications that have nothing to do with priority per se.

(P.S.: priority queues are traditionally implemented using binary heap arrays, so PriorityQueue's iterator is most likely returning its elements in the order stored in the array. In fact, the "3 5 9 22 12" output you reported is exactly consistent with a binary heap, given your insertion order. But that's an implementation detail that you don't need to know, and which you also cannot assume will be true across implementations and Java versions.)
[ November 24, 2007: Message edited by: Kelvin Lim ]
I agree. Here's the link:
subject: Ordering in PriorityQueue