Java Comparator Interface for Flexible Ordering

On Day 41, we used the Comparable interface to define natural ordering for elements. But what if we need different orderings for different situations? The Comparator interface provides this flexibility.

The Limitation of Comparable

Recall from Day 41: Elements implement Comparable<T> to define their natural ordering:

public class Task implements Comparable<Task> {
    private String name;
    private int priority;

    @Override
    public int compareTo(Task other) {
        return this.priority - other.priority;  // Natural ordering by priority
    }
}

Problem: Each class has only one natural ordering. What if we sometimes want to:

• Sort tasks by priority (high to low)
• Sort tasks by name (alphabetically)
• Sort tasks by deadline
• Create a min-heap instead of max-heap

We can't change compareTo() at runtime. We need a way to provide different comparison logic without modifying the class.

The Comparator Interface

Comparator<T> is a functional interface that defines a comparison strategy:

@FunctionalInterface
public interface Comparator<T> {
    int compare(T o1, T o2);
    // ... other default methods
}

Key difference from Comparable:

Creating a Comparator for Min-Heap

Goal: Create a min-heap where the smallest element has highest priority.

Strategy: Reverse the natural ordering by negating the comparison.

import java.util.Comparator;

public class MinHeapComparator<T extends Comparable<T>> implements Comparator<T> {
    @Override
    public int compare(T o1, T o2) {
        // Reverse the natural ordering
        return o2.compareTo(o1);  // Note: o2 compared to o1 (reversed)
    }
}

Usage:

// Create a priority queue with min-heap ordering
PriorityQueue<Integer> minHeap = new BinaryHeap<>(new MinHeapComparator<>());

minHeap.insert(50);
minHeap.insert(30);
minHeap.insert(70);

minHeap.best();  // Returns 30 (smallest value)

How it works: When bubbleUp() or bubbleDown() calls compare(a, b):

• Max-heap (natural): compare(50, 30) returns positive → 50 > 30 → 50 goes up
• Min-heap (reversed): compare(50, 30) returns negative → 30 > 50 → 30 goes up

Example: Task Priority with Multiple Criteria

Scenario: We have tasks with both priority and deadline. Sometimes we want:

1. High-priority tasks first (regardless of deadline)
2. Urgent tasks first (earliest deadline, regardless of priority)

Task class:

public class Task implements Comparable<Task> {
    private String name;
    private int priority;      // Higher value = more important
    private LocalDate deadline;

    public Task(String name, int priority, LocalDate deadline) {
        this.name = name;
        this.priority = priority;
        this.deadline = deadline;
    }

    // Natural ordering: by priority (high to low)
    @Override
    public int compareTo(Task other) {
        return this.priority - other.priority;
    }

    // Getters
    public int getPriority() { return priority; }
    public LocalDate getDeadline() { return deadline; }
    public String getName() { return name; }
}

Comparator 1: By priority (high to low) - uses natural ordering

// No comparator needed - this is the natural ordering
PriorityQueue<Task> byPriority = new BinaryHeap<>();

Comparator 2: By deadline (earliest first)

public class DeadlineComparator implements Comparator<Task> {
    @Override
    public int compare(Task t1, Task t2) {
        // Earlier deadline = higher priority (reverse date comparison)
        return t2.getDeadline().compareTo(t1.getDeadline());
    }
}

// Usage:
PriorityQueue<Task> byDeadline = new BinaryHeap<>(new DeadlineComparator());

Comparator 3: Multi-criteria (priority first, then deadline)

public class PriorityThenDeadlineComparator implements Comparator<Task> {
    @Override
    public int compare(Task t1, Task t2) {
        // First, compare by priority (high to low)
        int priorityComparison = t1.getPriority() - t2.getPriority();

        if (priorityComparison != 0) {
            return priorityComparison;  // Different priorities, done
        }

        // Same priority, compare by deadline (early to late)
        return t2.getDeadline().compareTo(t1.getDeadline());
    }
}

Using Lambda Expressions (Java 8+)

We have not explored lambda expressions in this course so you should not use them in assignments. However, for completeness, here's how you could define Comparators using lambdas.

Instead of creating separate classes, we can use lambda expressions:

// Min-heap for Integers
PriorityQueue<Integer> minHeap = new BinaryHeap<>((a, b) -> Integer.compare(b, a));

// Tasks by deadline (earliest first)
PriorityQueue<Task> byDeadline = new BinaryHeap<>(
    (t1, t2) -> t2.getDeadline().compareTo(t1.getDeadline())
);

// Tasks by name (alphabetical)
PriorityQueue<Task> byName = new BinaryHeap<>(
    (t1, t2) -> t1.getName().compareTo(t2.getName())
);

Conciseness: Lambda expressions make code much shorter for simple comparisons.

BinaryHeap with Comparator Support

Recall from last page, to support Comparator in the BinaryHeap class:

1. Added Comparator<T> comparator field
2. Added constructor accepting Comparator
3. Created compare(a, b) helper that uses comparator if present, otherwise compareTo()
4. Used compare(a, b) instead of a.compareTo(b) in bubbleUp() and bubbleDown()

This design demonstrates the Strategy Pattern from software design:

Problem: Need different algorithms (comparison strategies) that can be selected at runtime

Solution:

• Define a family of algorithms (different Comparators)
• Encapsulate each one
• Make them interchangeable

Benefits:

• Open/Closed Principle: Can add new comparison strategies without modifying existing code
• Single Responsibility: Comparison logic separated from heap logic
• Runtime flexibility: Can create different priority queues with different orderings

Summary

The Comparator interface adds powerful flexibility to priority queues:

Comparable (natural ordering):

• One ordering per class
• Defined at compile time
• Simpler for single-purpose classes

Comparator (custom ordering):

• Multiple orderings possible
• Defined at runtime
• More flexible for complex scenarios
• Enables min-heaps, multi-criteria sorting, and more

Best practice:

• Implement Comparable for the most common/natural ordering
• Provide Comparator constructors for alternative orderings