Java Priority Queue

Yesterday was sunny and all the snow on our deck has melted away, so my wife and I decided to grill for the first time this season. I believe the temperature went up to 58 F. The day was not as warm as I would have liked, but on occasions I went out just wearing a t-shirt. We grilled homemade hamburgers, potatoes, and corn. We fixed on the stovetop mushrooms with onions and garlic. All was very good and as usual we made too much food. That is fine because we will just warm up leftover today.

I spent some time working on the Java Priority Queue challenge from HackerRank. It was fun. I still do not understand why would developers use something else than a priority queue to solve the challenge. The idea seems to be to use the suggested data structure. In the context of the challenge, you can do whatever you wish. Perhaps that is thought by some as being creative. In the context of a development project, I think that is not good. Code gets complex and is hard to follow when people comes up and implements clever solutions. If the approach has an issue, it will be harder to find and address. Overall it just tends to increase the technical debt. That said, if the approach is faster and the team is OK with it, go to town!

The challenge had a single sample test case as illustrated by the following console capture:

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

Dan
Ashley
Shafaet
Maria


9
ENTER Paul 3.75 10
ENTER paul 3.75 20
ENTER Paul 3.75 30
ENTER Mary 3.75 50
ENTER john 4.0 100
SERVED
SERVED
SERVED
SERVED

paul

I created the second one.

The solution has three components. The most interesting seems to me to be the requirements for the comparator.

I implemented the code in Java using the Eclipse IDE. The testing scaffolding was provided by HackerRank.

The Student class follows:

/*
 * 
 */
class Student {
	
	// **** members ****
	String	name;
	int		id;
	double	cgpa;

	// **** constructor ****
	public Student(int id, String name, double cgpa) {
		this.name 	= name;
		this.id 	= id;
		this.cgpa 	= cgpa;
	}
	
	// **** get student name ****
	public String getName() {
		return this.name;
	}
	
	// **** get student ID ****
	public int getID() {
		return this.id;
	}
	
	// **** get student cgpa ****
	public double getCGPA() {
		return this.cgpa;
	}
	
	// **** student to string ****
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append(this.name);
		sb.append(" " + this.cgpa);
		sb.append(" " + this.id);
		return sb.toString();
	}
}

The comparator follows:

/*
 * Comparator for the priority queue
 */
class StudentComparator implements Comparator<Student> { 
    
	// **** ****
	public int compare(Student s1, Student s2) { 
	
		// **** compare on cgpa ****
		int cgpaDiff = Double.compare(s2.getCGPA(), s1.getCGPA());
		if (cgpaDiff != 0)
			return cgpaDiff;
		
		// **** compare on name ****
		int nameDiff = s1.getName().compareTo(s2.getName());
		if (nameDiff != 0)
			return nameDiff;
		
		// **** compare on ID ****
		return Integer.compare(s1.getID(), s2.getID());
	} 
} 

The Priorities class follows:

/*
 * 
 */
class Priorities {
	
	// **** constructor ****
	public Priorities() {
	}
	
	// **** ****
	public List<Student> getStudents(List<String> events) {

		// **** instantiate array list of students to return to caller ****
		List <Student> students 	= new ArrayList<Student>();

		// **** instantiate a priority queue to keep students sorted ****
		PriorityQueue<Student> pq 	= new PriorityQueue<Student>(events.size(), new StudentComparator());
		
		// **** traverse the list of events ****
		for (String e : events) {
						
			// **** process ENTER ****
			if (e.startsWith("ENTER", 0)) {
				
    			// **** split the event into fields ****
    			String[] fields = e.split(" ");
    			
    			// **** instantiate this student ****
    			Student student = new Student(Integer.parseInt(fields[3]), fields[1], Double.parseDouble(fields[2]));

    			// **** add student to the priority queue ****
    			pq.add(student);
			} 
			
			// **** process SERVED (highest priority) ****
			else {
				
//				// **** retrieve but NOT remove head of the queue ****
//				Student student = pq.peek();
//				System.out.println(student.toString());
				
				// **** retrieve and remove the head of the queue ****
				pq.poll();
			}	
		}
		
		// **** get the number of remaining students in the priority queue ****
		int n = pq.size();
		
		// **** build list of remaining students ****
		for (int i = 0; i < n; i++) {
			
			// **** remove next student from the priority queue ****
			Student student = pq.remove();
			
			// **** add the student to the list ****
			students.add(student);
		}
		
		// **** return list of remaining students ****
		return students;
	}
}

As usual I leave behind commented out code that I used to debug the approach and solution.

If you are interest the entire code is in my GitHub repository.

Hope you enjoyed this post. If you have comments or questions regarding this or any other post in this blog, or if you want me to provide help with a software development project, please leave me a note bellow. Requests will remain private.

Keep on reading and experimenting. It is the only way to make sure you fully understand what you are reading.

John

Follow me on Twitter:  @john_canessa

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.