Priority Queues/Comparators

Notes

Here is a link to the Java API docs for the Priority Queue class: https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

PriorityQueue is a Java class that implements a queue where elements in the queue have keys, and each item is sorted according to its key value.

Some links related to sorting in Java:

• Java/Comparable - built-in comparison functionality for objects
• Java/Comparators - standalone object for comparing two other objects

Example

The simple example below uses a custom comparator when constructing a priority queue. This implements a queue that adds the shortest Strings to the front of the queue. The driver code adds a series of strings whose lengths are in reverse alphabetical order, and we print the results of adding them to a Priority Queue object using our custom string length comparator (in which shorter strings come first), then the results of adding them to a normal Priority Queue object (which by default uses natural ordering, or lexicographical string ordering, alphabetical first).

Git Repo

This code is available on git.charlesreid1.com here: https://git.charlesreid1.com/cs/java/src/master/priority-queues/StringComparisonPQ.java

Code

Here is the actual class, which consists of a single main method that creates the two priority queues and operates on them, and the string length Comparator class.

The call to the PriorityQueue constructor that includes a comparator must specify the capacity of the Comparator. This capacity cannot be 0. If it is smaller than the number of items eventually added to the queue, the queue capacity is expanded, so the argument does not have much of an effect.

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

/** 
 * String Comparison Priority Queue.
 *
 * This class demonstrates the use of a comparator 
 * with the built-in PriorityQueue class
 * to allow sorting of data according to 
 * aribtrary criteria.
 *
 * Note that the built-in PriorityQueue class
 * uses a single templated type <E> as both 
 * the key and the value, so you can pass in a 
 * comparator and it will sort each element value
 * (which is also its own key) using that comparator.
 */
public class StringComparisonPQ {
	public static void main(String[] args) { 

		System.out.println("Length comparator:");

		// the initial capacity (first integer argument) does not seem to matter at all
		PriorityQueue<String> q = new PriorityQueue<String>(1,new StringLengthComparator());
		q.add("aaaaaaaaaaaaaaaaaaaaaaa");
		q.add("cccccccccccccccc");
		q.add("bbbbbbbbbbbbbbbbbbb");
		q.add("eeeeeeeeeee");
		q.add("ddddddddddddddd");
		q.add("yyyyyy");
		q.add("wwwwwwww");
		q.add("z");
		while(!q.isEmpty()) { 
			System.out.println(q.remove());
		}
		
		System.out.println();

		System.out.println("No comparator:");

		PriorityQueue<String> q2 = new PriorityQueue<String>(1);
		q2.add("aaaaaaaaaaaaaaaaaaaaaaa");
		q2.add("ddddddddddddddd");
		q2.add("bbbbbbbbbbbbbbbbbbb");
		q2.add("cccccccccccccccc");
		q2.add("z");
		q2.add("yyyyyy");
		q2.add("wwwwwwww");
		q2.add("eeeeeeeeeee");
		while(!q2.isEmpty()) { 
			System.out.println(q2.remove());
		}

	}
}

class StringLengthComparator implements Comparator<String> {
	public int compare(String s1, String s2) { 
		if(s1.length() < s2.length()) {
			// arg 22 greater than arg 1
			return -1;
		} else if(s1.length() > s2.length()) {
			// arg 1 greater than arg 2
			return 1;
		} else {
			// equals case
			return 0;
		}
	}
}

Output

$ javac StringComparisonPQ.java && java StringComparisonPQ
Length comparator:
z
yyyyyy
wwwwwwww
eeeeeeeeeee
ddddddddddddddd
cccccccccccccccc
bbbbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaaaaaaaaa

No comparator:
aaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbb
cccccccccccccccc
ddddddddddddddd
eeeeeeeeeee
wwwwwwww
yyyyyy
z