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.

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 alaphabetical order

Here is an example of using it with natural ordering for strings:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

below code explains the scenario.
 
// 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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