Java Priority Queue using Comparator

Photo by Marco Secchi on Unsplash

Introduction

In this post, we will cover how to create a Java Priority Queue with a Comparator. We are going to practice the problem defined at HackerRank. Let’s look at the problem description.

Problem Definition

Several students in a school are waiting to be served. There are two types of events that can take place: ENTER and SERVED.

• ENTER: A student with some priority enters the queue to be served.
• SERVED: The student with the highest priority is served (removed) from the queue.

We assign a unique id to each student entering the queue. The queue serves the students based on the following priority criteria:

1. The student having the highest Cumulative Grade Point Average (CGPA) is served first.
2. Any students having the same CGPA will be served by name in ascending case-sensitive alphabetical order.
3. Any students having the equal CGPA and name will be served in ascending order of the id.

The goal is to process all the given events and return all the students yet to be served in the priority order. Here are the sample input and output.

Sample Input

12
ENTER John 3.75 50
ENTER Mark 3.8 24
ENTER Shafaet 3.7 35
SERVED
SERVED
ENTER Samiha 3.85 36
SERVED
ENTER Ashley 3.9 42
ENTER Maria 3.6 46
ENTER Anik 3.95 49
ENTER Dan 3.95 50
SERVED

Sample Output

Dan
Ashley
Shafaet
Maria

Tasks

Let’s break down the problem description into pieces. How many components do we need? Can you guess?

We will add to or remove students from a priority queue based on some criteria. So, we need to create the Student, Priorities, and Comparator components:

The Student class should implement:

• The constructor Student(int id, String name, double cgpa).
• The method int getID() to return the id of the student.
• The method String getName() to return the name of the student.
• The method double getCGPA() to return the CGPA of the student.

The Custom Comparator class should implement priority criteria explained in the problem description area.

The Priorities class should implement the method List<Student> getStudents(List<String> events) to process all the given events and return all the students yet to be served in the priority order.

Create a Student class

Let’s create a student POJO class. You can also use the Lombok to reduce the boilerplate code.

class Student {
     private int id;
     private String name;
     private double cgpa;
public Student(int id, String name, double cgpa){
         this.id = id;
         this.name = name;
         this.cgpa = cgpa;
     }
public int getID(){
         return this.id;
     }
public String getName(){
         return this.name;
     }
public double getCGPA() {
         return this.cgpa;
     }
 }

Create a Custom Comparator

We create a custom comparator as our PriorityQueue orders its elements according to the specified comparator. We pass it to thePriorityQueue constructor as below:

new PriorityQueue<Student>(events.size(), new CustomComparator());

The custom comparator class implements the Comparator class and compares the students based on the following priority criteria:

1. The student having the highest Cumulative Grade Point Average (CGPA) is served first.
2. Any students having the same CGPA will be served by name in ascending case-sensitive alphabetical order.
3. Any students having the equal CGPA and name will be served in ascending order of the id.

class CustomComparator implements Comparator<Student>{ 
              
    @Override
    public int compare(Student s1, Student s2) {
if (s1.getCGPA() == s2.getCGPA()) 
            return s1.getName().compareTo(s2.getName()); 
       else if ((s1.getCGPA() == s2.getCGPA()) && (s1.getName()==s2.getName()))
            return ((Integer) s1.getID()).compareTo(s2.getID());
       else
            return ((Double) s2.getCGPA()).compareTo(s1.getCGPA()); 
    } 
}

The Priorities class

Here is how we return the students to be served in the priority order:

1. Create a PriorityQueue using the custom Comparator
2. Split the incoming events to retrieve the type of the events (ENTER or SERVED), and instance variables of the Student(id, name, cgpa).
3. For each event:

• Add the student to the queue, if the student is to be entered in the queue. Note that the objects are sorted by the custom Comparator as soon as we add them to the queue.
• Remove the student from the head of the queue, if the student is already served.

4. We add all the remaining students from the queue to a list and return them

class Priorities {
public List<Student> getStudents(List<String> events){
        List<Student> names = new ArrayList<Student>();
        PriorityQueue<Student> queue = new PriorityQueue<Student>();>(events.size(), new CustomComparator());
     
        for(String event: events){
             String[] splitted = event.split(" ");
             if(splitted[0].equals("ENTER")){
                int id  = Integer.parseInt(splitted[3]);
                String name = splitted[1];
                double cgpa = Double.parseDouble(splitted[2]);
                queue.add(new Student(id,name,cgpa));
             } else if (splitted[0].equals("SERVED")){
                queue.poll();
             }
        }
 
        while (!queue.isEmpty()) {
          names.add(queue.poll());
        }
return names;
    }
}