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;
}
}

Software Engineer, Oracle Certified Java Programmer, http://suleymanyildirim.org/

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

How to successfully migrate an Enterprise to AWS

Technical structure of WorkQuest

Winter is Coming - How to prepare for job interviews

READ/DOWNLOAD#< Sopa De Letras En Español Letra Gr

Types of Web Portals You Can Develop this 2018

Top 7 Replies by Programmers when their programs don’t work:

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Suleyman Yildirim

Suleyman Yildirim

Software Engineer, Oracle Certified Java Programmer, http://suleymanyildirim.org/

More from Medium

Solid Principle in Java

Why Spring Boot is called opinionated?

Spring Boot Initializr

Lambda Expression in Java