Sorting with PriorityQueue and Comparator in Java

In Java, the PriorityQueue is a powerful data structure that allows us to manage elements based on their priority. By combining it with a Comparator, we can define custom sorting rules for complex objects, such as students. This article demonstrates how to use a PriorityQueue with a custom Comparator to prioritize students based on their GPA, name, and ID.

---

Overview of the Scenario

Imagine a Student class with the following attributes:

• cgpa (Cumulative Grade Point Average)
• name
• id

We want to implement a PriorityQueue that:

1. Orders students by their cgpa in descending order (higher GPA gets higher priority).
2. Breaks ties by ordering alphabetically by name.
3. Further breaks ties by ordering by id in ascending order.

---

The Student Class

Here’s the Student class:

class Student {
    private double cgpa;
    private String name;
    private int id;

    public Student(double cgpa, String name, int id) {
        this.cgpa = cgpa;
        this.name = name;
        this.id = id;
    }

    public double getCgpa() {
        return cgpa;
    }

    public String getName() {
        return name;
    }

    public int getId() {
        return id;
    }

    @Override
    public String toString() {
        return "Student{name='" + name + "', cgpa=" + cgpa + ", id=" + id + "}";
    }
}

---

Custom Comparator for Sorting Students

We can create a Comparator using Java’s functional style with the Comparator utility methods:

Comparator<Student> studentComparator = Comparator
        .comparingDouble(Student::getCgpa).reversed()
        .thenComparing(Student::getName)
        .thenComparing(Student::getId);

Explanation:

1. comparingDouble(Student::getCgpa).reversed():
   • Sorts students by their GPA in descending order.
2. thenComparing(Student::getName):
   • If two students have the same GPA, they are sorted alphabetically by name.
3. thenComparing(Student::getId):
   • If the GPA and name are the same, students are sorted by ID in ascending order.

---

Using PriorityQueue with the Custom Comparator

The PriorityQueue is initialized with the custom Comparator:

PriorityQueue<Student> queue = new PriorityQueue<>(studentComparator);

This ensures that elements in the queue are always arranged based on the defined priority. The student with the highest priority is at the front of the queue.

---

Complete Example

Here’s a complete program that demonstrates the functionality:

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

public class PriorityQueueExample {
    public static void main(String[] args) {
        // Custom comparator for the PriorityQueue
        Comparator<Student> studentComparator = Comparator
                .comparingDouble(Student::getCgpa).reversed()
                .thenComparing(Student::getName)
                .thenComparing(Student::getId);

        // PriorityQueue with custom comparator
        PriorityQueue<Student> queue = new PriorityQueue<>(studentComparator);

        // Adding students to the queue
        queue.add(new Student(3.9, "Alice", 3));
        queue.add(new Student(3.9, "Bob", 2));
        queue.add(new Student(3.5, "Charlie", 1));
        queue.add(new Student(3.9, "Alice", 1));

        // Processing students based on priority
        System.out.println("Students in order of priority:");
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}

---

Output

For the input students:

• Alice (CGPA: 3.9, ID: 3)
• Bob (CGPA: 3.9, ID: 2)
• Alice (CGPA: 3.9, ID: 1)
• Charlie (CGPA: 3.5, ID: 4)

The output will be:

Students in order of priority:
Student{name='Alice', cgpa=3.9, id=3}
Student{name='Alice', cgpa=3.9, id=4}
Student{name='Bob', cgpa=3.9, id=2}
Student{name='Charlie', cgpa=3.5, id=1}

---

Key Points

1. PriorityQueue with Comparator:
   • The PriorityQueue ensures that the student with the highest priority (as defined by the Comparator) is always at the head of the queue.
2. Comparator with thenComparing:
   • Allows defining multi-level sorting criteria in a clear and readable manner.
3. Order Preservation:
   • The PriorityQueue processes elements based on the priority, not the insertion order.

---

Use Cases

• Scheduling: Prioritize tasks or jobs based on multiple criteria, like deadlines and importance.
• Event Processing: Handle events based on priority levels, such as in simulations or real-time systems.
• Data Processing: Sort complex data objects efficiently during insertion and extraction.

---

This example highlights the flexibility of combining PriorityQueue and Comparator to handle complex sorting logic dynamically and efficiently.