Time flies when you are having fun; at least that is how the saying goes. Today is Saturday and I am on my second and last block of the day. After breakfast I prepared the pizza dough and put it in a bowl covered with plastic film for it to rise. During the break between blocks my wife and I checked the dough. It is touching the plastic. It has tripled its size.
For lunch we are going to make and bake a few small and thin pizzas. We are going to mix and match toppings and are expecting to have a few leftover pizzas. Tomorrow we are going to make “baba” (an Italian yeast cake). Will have a few and the rest with the pizzas will be delivered to my oldest son.
On the last issue of Communications of the ACM I read an article titled “A* Search: what’s in a name?”. The article deals with the name of the algorithm. 
I know about the algorithm but have never used it. I decided that it would be nice to experiment with it. I will cover the algorithm and some code in my next bog (tomorrow).
This post deals with the PriorityQueue class in Java. The A* Search algorithm makes use of a priority queue with a custom comparator. In preparation I decided to generate this post.
I wrote the code for this post using Visual Studio Code on a Windows 10 machine. The code is Java 8 compatible. I also decided to experiment with comparators and lambdas. They are a good items to have in your knowledge toolkit.
11 5 2 6 9 3 8 4 11 1 7 10 8 Garielle 4.1 Peter 3.1 Jane 2.8 John 4.1 Ann 2.1 Joseph 3.1 Mary 3.5 Carmen 4.1 main <<< arr: [5, 2, 6, 9, 3, 8, 4, 11, 1, 7, 10] main <<< grades: [4.1 Garielle, 3.1 Peter, 2.8 Jane, 4.1 John, 2.1 Ann, 3.1 Joseph, 3.5 Mary, 4.1 Carmen] experiment <<< size: 11 experiment <<< pq: [1, 2, 4, 3, 5, 8, 6, 11, 9, 7, 10] experiment <<< pq: 1 2 3 4 5 6 7 8 9 10 11 experiment <<< pq: [11, 10, 8, 6, 9, 5, 4, 2, 1, 3, 7] experiment <<< pq: 11 10 9 8 7 6 5 4 3 2 1 experiment <<< arr: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] experiment <<< pq: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] experiment <<< pq: 1 2 3 4 5 6 7 8 9 10 11 experiment <<< studentGrades: [2.1 Ann, 2.8 Jane, 3.1 Joseph, 4.1 Carmen, 4.1 Garielle, 3.1 Peter, 3.5 Mary, 4.1 John] experiment <<< studentGrades: 2.1 Ann 2.8 Jane 3.1 Joseph 3.1 Peter 3.5 Mary 4.1 Carmen 4.1 Garielle 4.1 John
The first line of the input indicates the number of integers in the following line. We will read into an array. Will then use a priority queue and experiment with it.
The third line contains a number. It indicates the number of lines that follow. Each line start with the name of a student (yes, I like to keep things casual and on a first-name basis) followed by a GPA (I could just called it a grade but the example will show ordering).
The output is separated by blank lines. It seems that we read and display the data to verify our input. We then run four experiments which will become obvious as we look at the code for the test scaffolding.
// **** open scanner ****
static Scanner sc = new Scanner(System.in);
/*
* Test scaffolding.
*/
public static void main(String[] args) {
// **** read the number of elements for the queue ****
int n = sc.nextInt();
// **** read the line with the integers ****
sc.nextLine();
String buffer = sc.nextLine();
// **** extract the strings holding integers from the buffer ****
String[] strs = buffer.split(" ");
// **** create and populate an array of integers ****
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(strs[i]);
}
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** read number of students and grades ****
int m = sc.nextInt();
// **** read the student grades into an array ****
Grade[] grades = new Grade[m];
sc.nextLine();
for (int i = 0; i < m; i++) {
String str = sc.nextLine();
String[] vals = str.split(" ");
grades[i] = new Grade(vals[0], Double.parseDouble(vals[1]));
}
// ???? ????
System.out.println("main <<< grades: " + Arrays.toString(grades) + "\n");
// **** experiemnt with a PriorityQueue ****
experiment(arr, grades);
// **** close scanner ****
sc.close();
}
We do what we described above. We first read the line of integers and load an array with the values in the order they were entered.
We then read the lines with grades into an array of Grades. Both arrays are passed to the experiment() function which we will look at shortly.
/*
* Grade class. Will use it to sort elements in a priority queue by name and gpa.
*/
class Grade {
// **** members ****
public String name;
public double gpa;
// **** constructor ****
public Grade(String name, double gpa) {
this.name = name;
this.gpa = gpa;
}
// **** toString ***
public String toString() {
return this.gpa + " " + this.name;
}
}
The Grades class contains a name and a GPA. We have a simple constructor and a toString() method. We display the GPA, a blank space and the name of the student.
/*
* Experiment with the PriorityQueue class.
*/
public class PriorityQ {
/*
*
*/
static void experiment(int[] arr, Grade[] grades) {
// **** get the size of the array ****
int size = arr.length;
// ???? ????
System.out.println("experiment <<< size: " + size);
// **** overwrite the initial size of the priority queue ****
size = 3;
// **** create a PriorityQueue without comparator ****
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(size);
// **** add the array values to the priority queue ****
for (int i = 0; i < arr.length; i++) {
pq.add(arr[i]);
}
// **** display the priority queue (random order) ****
System.out.println("experiment <<< pq: " + pq.toString());
// **** remove in order elements from the queue (lower to higher) ***
System.out.print("experiment <<< pq: ");
while (pq.size() != 0) {
System.out.print(pq.remove() + " ");
}
System.out.println("\n");
// **** PriorityQueue with comparator (higher to lower) ****
pq = new PriorityQueue<Integer>(size, (Integer a, Integer b) -> {
int result = 0;
if (a < b) { result = 1; } else if (a > b) {
result = -1;
}
return result;
});
// **** add the array values to the priority queue ****
for (int i = 0; i < arr.length; i++) {
pq.add(arr[i]);
}
// **** display the priority queue (random order) ****
System.out.println("experiment <<< pq: " + pq.toString());
// **** remove in order elements from the queue (higher to lower) ***
System.out.print("experiment <<< pq: ");
while (pq.size() != 0) {
System.out.print(pq.remove() + " ");
}
System.out.println("\n");
// **** create a PriorityQueue without comparator or size ****
pq = new PriorityQueue<Integer>();
// **** sort the array ****
Arrays.sort(arr);
// *** display the array ****
System.out.println("experiment <<< arr: " + Arrays.toString(arr));
// **** add the array values to the priority queue ****
for (int i = 0; i < arr.length; i++) {
pq.add(arr[i]);
}
// **** display the priority queue (random order) ****
System.out.println("experiment <<< pq: " + pq.toString());
// **** remove in order elements from the queue (lower to higher) ***
System.out.print("experiment <<< pq: ");
while (pq.size() != 0) {
System.out.print(pq.remove() + " ");
}
System.out.println("\n");
// **** create a PriorityQueue with comparator ****
PriorityQueue<Grade> studentGrades = new PriorityQueue<Grade>((Grade g1, Grade g2) -> {
int result = 0;
if (g1.gpa < g2.gpa) {
result = -1;
} else if (g1.gpa == g2.gpa) {
int comp = g1.name.compareTo(g2.name);
result = comp;
} else {
result = 1;
}
return result;
});
// **** add the grade values to the priority queue ****
for (int i = 0; i < grades.length; i++) {
studentGrades.add(grades[i]);
}
// **** display the priority queue (random order) ****
System.out.println("experiment <<< studentGrades: " + studentGrades.toString());
// **** remove in order elements from the queue (lower to higher) ***
System.out.print("experiment <<< studentGrades: ");
while (studentGrades.size() != 0) {
System.out.print(studentGrades.remove() + " ");
}
System.out.println("\n");
}
}
We first create a PriorityQueue with a size and no comparator. We add the values in the array and display the contents of the priority queue. We then remove each element from the head of the queue. Note that the contents are not in the expected order, but the contents of the queue are removed in the expected order.
We then create a new priority queue with size and a comparator. We add the contents of the array. We display the priority queue and then remove the elements from the head. Note once again that the string conversion does not show the actual order. When we remove the elements they show up in monotonically decreasing order as expected. Take a closer look at the comparator.
We now proceed to create a new priority queue without size of comparator. We sort the elements in the array and display them. As expected they are in ascending order. Note that when we display the contents of the queue and remove the contents from the head, they both are in order. If you read the description for the PriorityQueue class in the Oracle documentation, the order is not guaranteed even if one uses an iterator.
On our last experiment, we create a priority queue with a comparator. We add the student grades and then display the queue. Note that the contents of the queue are in a different order that we entered them and not in a sorted order as specified with the comparator. When we remove the elements from the head they follow the order we desire. The GPA values are in increasing order. When a GPA value is shared by multiple students, the names of the students are in ascending order by name.
I experimented with the priority queue in many different ways that I did not 
document in this post. If you are new to this class or just wish to refresh your knowledge, be creative and see if what your expected output matches the actual one.
My wife is calling me to start with the pizzas. Will finish this post and will help with lunch. Actually I am getting a little hungry.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a message using the following address: john.canessa@gmail.com. All messages will remain private.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
John
Twitter: @john_canessa