PriorityQueue

The Queue interface has different implementations with different characteristics. This topic will be dedicated to one of them: the PriorityQueue class. You will explore its behavior, understand how it stores elements, and learn how to use it when working with custom classes.

Brief overview

This class doesn't operate on a FIFO basis like a regular queue. It is based on a priority heap and is useful when you need to store elements by their priority. By default, it applies natural ordering to comparable objects, or custom ordering using a comparator which can be set when creating a PriorityQueue object by passing a comparator to its constructor.
PriorityQueue is an unbounded queue. It has an initial capacity of 11 elements but can grow in size automatically. Besides that, you can set the default capacity manually using the appropriate constructor.

PriorityQueue with basic types

In this section, we will explore how PriorityQueue operates with basic data types that implement the compareTo() method of the Comparable interface.

    Queue<Integer> queue = new PriorityQueue();
    queue.add(5);
    queue.add(15);
    queue.add(20);
    queue.add(10);

    System.out.println(queue.poll()); // 5
    System.out.println(queue.poll()); // 10

If we were using a regular queue, the second element would be 15, and 10 would be added at the tail of the queue.

Thanks to PriorityQueue's natural ordering behavior, here 10 is stored after 5 in the queue.
In the example above, we saw how PriorityQueue orders numeric values. Now let's see how PriorityQueue stores strings. Here the head element is A: when working with strings, PriorityQueue compares elements lexicographically, and A is the smallest element.

    Queue<String> queue = new PriorityQueue();
    queue.add("B");
    queue.add("C");
    queue.add("D");
    queue.add("A");

    System.out.println(queue.poll()); // A
    System.out.println(queue.poll()); // B

PriorityQueue with custom classes

Now that we've seen how PriorityQueue works with basic types, let's study some examples with custom classes. First, let's create a Person class with one field and the PersonComparator class implementing the Comparator interface to pass its object to the PriorityQueue constructor. Without this, the application will throw a ClassCastException, since you can't add non-comparable objects to the PriorityQueue.

class Person {
    private int mathScore;

    public Person(int age) {
        this.mathScore = age;
    }

    // getter

    @Override
    public String toString() {
        return "Person{" +
                "mathScore=" + mathScore +
                '}';
    }
}

class PersonComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        return Integer.compare(p1.getMathScore(), p2.getMathScore());
    }
}

The compare() implementation will store the smallest value in the head. Now let's create a queue passing the comparator to its constructor, and add some elements to it:

    Queue<Person> queue = new PriorityQueue(new PersonComparator());
    queue.add(new Person(90));
    queue.add(new Person(80));
    queue.add(new Person(85));

    System.out.println(queue.poll()); // 80
    System.out.println(queue.poll()); // 85

In this example, we have only one field in the class. But what if we had more than one? After updating the code, we will have the compare() method based on two field comparisons, where the head will store the element with the biggest value.

class Person {
    private int mathScore;
    private int physicsScore;

    public Person(int mathScore, int physicsScore) {
        this.mathScore = mathScore;
        this.physicsScore = physicsScore;
    }
 
    // getters

    @Override
    public String toString() {
        return "Person{" +
                "mathScore=" + mathScore +
                ", physicsScore=" + physicsScore +
                '}';
    }
}

class PersonComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        // Part 1
        int result = (p1.getMathScore() > p2.getMathScore()) ? -1 :
                ((p1.getMathScore() == p2.getMathScore()) ? 0 : 1);
        if (result != 0) return result;

        // Part 2
        return (p1.getPhysicsScore() > p2.getPhysicsScore()) ? -1 :
                ((p1.getPhysicsScore() == p2.getPhysicsScore()) ? 0 : 1);
    }
}

Here, we first compare mathScore and if it's equal, we compare physicsScore. Let's analyze the compare() method code so that you have a better understanding of how it works. This is a slightly modified version of the code that is executed when calling the Integer.compare() method. If we used it in our queue without modification, the smallest element would be stored in the head, so we have to change its code to store the biggest element in the head. In the first part, the ternary operator checks if p1.getMathScore() is greater than p2.getMathScore(). If it is, it returns -1, if not, they are checked for equality. If they are equal, the ternary operator returns 0, otherwise 1. After that, the if block checks the result variable value: if it is not 0, the values aren't equal, and the method returns the result variable value. If the value is 0, the variables are equal, so it needs to perform an additional comparison of the physicsScore field.
Now let's add elements to the queue and see how this code works:

    Queue<Person> queue = new PriorityQueue(new PersonComparator());
    queue.add(new Person(90, 95));
    queue.add(new Person(90, 100));
    queue.add(new Person(80, 100));
    queue.add(new Person(80, 95));
    queue.add(new Person(85, 90));

    System.out.println(queue.poll()); // Person{mathScore=90, physicsScore=100}
    System.out.println(queue.poll()); // Person{mathScore=90, physicsScore=95}
    System.out.println(queue.poll()); // Person{mathScore=85, physicsScore=90}
    System.out.println(queue.poll()); // Person{mathScore=80, physicsScore=100}
    System.out.println(queue.poll()); // Person{mathScore=80, physicsScore=95}

This is exactly the behavior we expected. The elements are sorted according to the logic we implemented. The application first sorts the elements based on the mathScore value: if these values are equal, it compares the physicsScore values.

Conclusion

In this topic, we discussed the PriorityQueue class and explained how to use it in practice. You learned how PriorityQueue operates with both basic types and custom classes. You can write any logic to compare its elements. For this purpose, we have prepared some practical tasks for you. So, study the code examples in the theory section carefully and proceed to practice!