• 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

Ordering in PriorityQueue

 
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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();
while(it.hasNext())
{
System.out.println(it.next());
}
}
}
Output -
3
5
9
22
12

I couldnt understand what kind of ordering is it. Can somebody please help me on this.
Thanks in advance.
 
Ranch Hand
Posts: 513
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
Mohit Jain
Ranch Hand
Posts: 74
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 513
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
"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 ]
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic