Custom Comparator for Priority Queue in Java

In the world of data structures, the Priority Queue serves as a handy tool that allows elements to be processed based on their priority rather than their insertion order. In Java, the PriorityQueue class provides a versatile way to implement this data structure. By default, elements are ordered based on their natural ordering or their comparable natural order. However, there may be times when you want to impose a custom order on your elements. This is where a Custom Comparator comes in!

Understanding the Basics

The PriorityQueue in Java is part of the Java Collections Framework and is defined in the java.util package. It implements the Queue interface and provides a convenient way to access the highest (or lowest) prioritized element in constant time, while insertion and removal are performed in logarithmic time.

The standard most useful constructors take a Comparator as an argument, so you can easily adapt the ordering based on your requirements. Here’s the basic syntax for creating a PriorityQueue with a custom comparator:

PriorityQueue<Type> queue = new PriorityQueue<Type>(Comparator);

Creating a Custom Comparator

To create a custom comparator in Java, you need to implement the Comparator interface, which requires the implementation of the compare(T o1, T o2) method. This method compares its two arguments for order. Here’s a simple example:

Let’s say we have a class Person representing individuals with a name and an age, and we want to prioritize people by age rather than the default:

class Person {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

Next, we implement a custom comparator for the Person class:

class AgeComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        return Integer.compare(p1.age, p2.age); // Compare by age
    }
}

Using the Custom Comparator with PriorityQueue

Now that we have our AgeComparator, we can instantiate a PriorityQueue with it like so:

PriorityQueue<Person> priorityQueue = new PriorityQueue<>(new AgeComparator());

Let’s add some Person objects to our priority queue:

priorityQueue.add(new Person("Alice", 30));
priorityQueue.add(new Person("Bob", 25));
priorityQueue.add(new Person("Charlie", 35));

When we poll the queue, it will return the Person with the lowest age first:

while (!priorityQueue.isEmpty()) {
    Person p = priorityQueue.poll();
    System.out.println(p.name + " - " + p.age);
}

Output:

Bob - 25
Alice - 30
Charlie - 35

Multiple Comparators

One of the powerful features of custom comparators is the ability to implement multiple comparisons. For example, if we want to compare by age first, but in case of a tie, we’ll sort by name alphabetically, we can do this easily:

class AgeNameComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        int ageComparison = Integer.compare(p1.age, p2.age);
        if (ageComparison != 0) {
            return ageComparison; // Different ages
        }
        return p1.name.compareTo(p2.name); // Same age, compare by name
    }
}

You can utilize this comparator in the same way:

PriorityQueue<Person> priorityQueue = new PriorityQueue<>(new AgeNameComparator());

Summary of Custom Comparator Advantages

1. Custom Ordering: You can define any order that fits your specific requirements.
2. Reusability: Once implemented, custom comparators can be reused across different PriorityQueue instances.
3. Encapsulation: Compare logic is encapsulated, making your code cleaner and easier to manage.

In this blog post, we've covered how to create and use custom comparators in Java's PriorityQueue. Whether you're preparing for an interview on data structures and algorithms or just expanding your Java skillset, understanding how to utilize custom comparators effectively can significantly enhance your programming toolkit. You’ll find that with practice, using custom comparators will become second nature, allowing you to tackle more complex data structures and algorithms with ease.