Ordering Queue Using Comparator Interface and PriorityQueue

The basic use of Queue class is to provide a data structure which allows storing objects in a First in First out(FIFO) format. But sometimes one wants to maintain the ordering, based on some other metric. This is exactly the purpose of PriorityQueue, another Queue implementation. You provide it a Comparator, and it does the rest for you.

also read:

This queue orders elements according to an order specified at construction time, which is specified either according to their natural order, or according to a Comparator, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects.
PriorityQueue works just as any other Queue implementation, and you don’t even need to learn any new methods. Instead of performing FIFO ordering, though, a PriorityQueue orders its items by using the Comparator interface. If you create a new queue and don’t specify a Comparator, you get what’s called natural ordering, which applies to any classes that implement Comparable. The head of this queue is the least element with respect to the specified ordering. For string values, for instance, this places string values in the natural alphabetical order.
Here is an example of using it with natural ordering for strings:

// array of alphabets stored in an unordered way
String[] alphabets = {"b", "e", "d", "h","j", "a", "c", "f", "g", "i",
			"B", "E", "D", "H","J", "A", "C", "F", "G", "I"};

PriorityQueue<string> pq = new PriorityQueue<string>(20);

// Fill up with data, in an odd order
for (int i=0; i<20; i++) {
	pq.offer(alphabets[i]);
}

// Print out and check ordering
for (int i=0; i<20; i++) {
	System.out.println(pq.poll( ));
}

Since no Comparator implementation is given to PriorityQueue, it orders the alphabets in the alphabetical order from lowest ascii valued alphabet to the highest, even though they’re not added to the queue in that order.
So when peeling off elements, the lowest valued alphabets comes out first. The uppercase alphabets have lower ascii values than lowercase alphabets so they appear above lowercase alphabets.

Now, this queue implementation really starts working its magic when you provide your own comparator implementation as an argument to the PriorityQueue class constructor, as is shown in the next example.

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueTester {

	public static void main(String[] args) {
	  String[] alphabets = {"b", "e", "d", "h","j",
							"a", "c", "f", "g", "i",
							"B", "E", "D", "H","J",
							"A", "C", "F", "G", "I"};

	  PriorityQueue<string> pq = new PriorityQueue<string>(20,
			new Comparator<string>( ) {
				// overriding the compare method
				public int compare(String i, String j) {
					return i.compareToIgnoreCase(j);
				}
			}
	  );

	  // Fill up with data, in an odd order
	  for (int i=0; i<20; i++) {
		pq.offer(alphabets[i]);
	  }

	  // Print out and check ordering
	  for (int i=0; i<20; i++) {
		System.out.println(pq.poll( ));
	  }
	}
}

Since, the comparator sorts the alphabets ignoring the case, the alaphabets come out from the queue with alphabets of both cases adjacent to each other.

Comments

comments

About Krishna Srinivasan

He is Founder and Chief Editor of JavaBeat. He has more than 8+ years of experience on developing Web applications. He writes about Spring, DOJO, JSF, Hibernate and many other emerging technologies in this blog.

Comments

  1. very nice.. for more java examples visit java2novice.com site

Speak Your Mind

*