A few years ago, I was reviewing code for a colleague who had built a task-scheduling system for a background processing engine. He was using a standard ArrayList to hold the tasks and calling Collections.sort() every single time a new task was added to ensure the highest-priority job was always at the top. It worked perfectly during the demo with ten tasks. But when we hit production with ten thousand tasks per second, the CPU usage spiked to 90% and the system practically ground to a halt. The bottleneck was obvious: sorting an entire list over and over is a massive waste of resources when you only actually care about the single most important element.

That's where the PriorityQueue comes in. Unlike a standard Queue, which follows a strict First-In-First-Out (FIFO) order, a PriorityQueue ensures that the element with the "highest priority" is always at the head of the queue. In Java, this is implemented using a binary heap. If you're not familiar with heaps, don't let the name intimidate you; it's essentially a tree-based structure that keeps the smallest (or largest) element at the root, allowing us to insert new items and remove the top item in logarithmic time—O(log n)—which is vastly more efficient than re-sorting a list.

The Mechanics of the Min-Heap

By default, Java's PriorityQueue is a min-heap. This means the element that compares as "least" will be the first one served. I've seen many developers get tripped up by this, expecting the largest number to come out first. If you put the integers 10, 1, and 5 into a PriorityQueue, the first call to poll() will give you 1, not 10.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(1);
pq.add(5);

System.out.println(pq.poll()); // Outputs 1
System.out.println(pq.poll()); // Outputs 5

One thing to keep in mind: the PriorityQueue does not guarantee any specific order when you iterate over it using an iterator or a for-each loop. It only guarantees that the head of the queue is the smallest element. If you need the whole collection sorted, you'll have to poll the elements out one by one.

Defining Custom Priority with Comparators

In the real world, you're rarely just storing integers. You're usually storing objects—like a Ticket or a UserRequest—and you need to define what "priority" actually means for those objects. You have two main ways to handle this: implementing the Comparable interface within your class, or passing a Comparator to the PriorityQueue constructor.

I generally prefer the Comparator approach because it's more flexible. It allows you to change the priority logic without modifying the data class itself. For example, if you want a max-heap (where the highest value comes first), you can simply use Collections.reverseOrder() or a custom lambda expression.

class Task {
    String name;
    int priorityLevel;

    Task(String name, int priorityLevel) {
        this.name = name;
        this.priorityLevel = priorityLevel;
    }
}

// We want the highest priorityLevel to be processed first
PriorityQueue<Task> taskQueue = new PriorityQueue<>((a, b) -> b.priorityLevel - a.priorityLevel);

taskQueue.add(new Task("Fix minor typo", 1));
taskQueue.add(new Task("Fix production crash", 10));
taskQueue.add(new Task("Update documentation", 2));

while (!taskQueue.isEmpty()) {
    System.out.println("Processing: " + taskQueue.poll().name);
}
// Output: 
// Processing: Fix production crash
// Processing: Update documentation
// Processing: Fix minor typo

Notice the lambda (a, b) -> b.priorityLevel - a.priorityLevel. By subtracting a from b instead of the usual a - b, we effectively flip the natural ordering, turning our min-heap into a max-heap. Just be careful with subtraction if your values can be very large or negative, as you might hit integer overflow; in those cases, Integer.compare(b.val, a.val) is the safer, professional choice.

📋 Practical Task

Exercise: Hospital Emergency Room Triage System

You are tasked with building a triage system for a hospital. Patients arrive at different times with different severity levels. The hospital must always treat the patient with the highest severity first. If two patients have the same severity, the one who arrived first should be treated first (FIFO).

Requirements:

• Create a Patient class with the following fields: String name, int severity (1 to 10, where 10 is critical), and long arrivalTime.
• Implement a TriageSystem class that uses a PriorityQueue to manage patients.
• The PriorityQueue must be configured so that:
  1. Patients with higher severity are polled first.
  2. If severity is equal, the patient with the lower arrivalTime (the one who arrived earlier) is polled first.
• Write a main method to simulate the following scenario:
  • Patient "Alice" arrives with severity 5.
  • Patient "Bob" arrives with severity 10.
  • Patient "Charlie" arrives with severity 10.
  • Patient "David" arrives with severity 2.
• Poll and print the patients in the order they should be treated.