PriorityQueue ​

We know that a Queue is a First In First Out (FIFO) structure.

In a bank counter service, if there is only one counter but many people are waiting, what should we do?

Each person can take a number, for example: A1, A2, A3... Then, they will be served in order of their numbers. This is essentially a Queue.

Now, suppose a VIP customer arrives with the number V1. Although the current customers in line have numbers A10, A11, A12..., the next customer called at the counter will be V1.

At this point, we realize that to implement the “VIP jump-the-line” service, a regular Queue will not suffice because it strictly follows the FIFO principle. What we need is a priority queue: PriorityQueue.

The difference between PriorityQueue and Queue is that the order of removal from a PriorityQueue is based on the priority of the elements. When calling remove() or poll() on a PriorityQueue, it always returns the element with the highest priority.

To use a PriorityQueue, we must define a "priority" for each element. Let’s examine the behavior of PriorityQueue through a code example:

import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> q = new PriorityQueue<>();
        // Add 3 elements to the queue:
        q.offer("apple");
        q.offer("pear");
        q.offer("banana");
        System.out.println(q.poll()); // apple
        System.out.println(q.poll()); // banana
        System.out.println(q.poll()); // pear
        System.out.println(q.poll()); // null, because the queue is empty
    }
}

The order in which we inserted the elements is "apple", "pear", "banana", but the order in which they are removed is "apple", "banana", "pear". This is because "apple" comes first in string sorting, and "pear" comes last.

Therefore, elements added to a PriorityQueue must implement the Comparable interface, as the PriorityQueue will determine the order of removal based on the sorting of the elements.

What if the elements we want to add do not implement the Comparable interface? The PriorityQueue allows us to provide a Comparator object to determine the order of two elements. Let’s implement a PriorityQueue using a bank queue service as an example:

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<User> q = new PriorityQueue<>(new UserComparator());
        // Add 3 elements to the queue:
        q.offer(new User("Bob", "A1"));
        q.offer(new User("Alice", "A2"));
        q.offer(new User("Boss", "V1"));
        System.out.println(q.poll()); // Boss/V1
        System.out.println(q.poll()); // Bob/A1
        System.out.println(q.poll()); // Alice/A2
        System.out.println(q.poll()); // null, because the queue is empty
    }
}

class UserComparator implements Comparator<User> {
    public int compare(User u1, User u2) {
        if (u1.number.charAt(0) == u2.number.charAt(0)) {
            // If both users' numbers start with 'A' or 'V', compare their numbers:
            return u1.number.compareTo(u2.number);
        }
        if (u1.number.charAt(0) == 'V') {
            // If u1's number starts with 'V', it has a higher priority:
            return -1;
        } else {
            return 1;
        }
    }
}

class User {
    public final String name;
    public final String number;

    public User(String name, String number) {
        this.name = name;
        this.number = number;
    }

    public String toString() {
        return name + "/" + number;
    }
}

The key to implementing the PriorityQueue lies in the provided UserComparator object, which is responsible for comparing two elements (the smaller one comes first). The UserComparator always prioritizes numbers starting with 'V' and only compares the numbers when the prefixes are the same.

The comparison logic in the UserComparator above has an issue; it will place A10 ahead of A2. Please try to fix this error.

Summary ​

• The PriorityQueue implements a priority queue: when retrieving elements from the head, it always gets the element with the highest priority.
• PriorityQueue sorts elements by their default comparison order (the elements must implement the Comparable interface) but can also use a Comparator for custom sorting (elements do not need to implement the Comparable interface).