Java PriorityQueue Comparator: Control Ordering

When you create a Java PriorityQueue without a comparator, it orders elements by their natural ordering. That works for types like Integer or String, but many real-world queues need a different rule. The java priorityqueue comparator argument lets you define exactly how elements are prioritized without changing the element class itself.

The comparator is passed as the second constructor argument. The queue uses it to determine the relative priority of any two elements. This is the mechanism that decides which element is removed first by poll() or peek().

How PriorityQueue Uses a Comparator

A PriorityQueue is a binary heap. The comparator defines the heap invariant: for any two elements, the one that compares as "less" according to the comparator sits closer to the root. When you call offer(), the queue sifts the new element up until the heap property holds. When you call poll(), it removes the root and sifts the last element down.

The comparator is called repeatedly during these operations. It must be consistent and provide a total ordering, otherwise the heap can become corrupted and the queue will not behave correctly.

Basic Comparator Syntax with PriorityQueue

Here is the simplest way to create a priority queue with a custom comparator:

PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.naturalOrder());
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

Comparator.naturalOrder() returns a comparator that uses the natural ordering of the elements, which is the same as the no-arg constructor. Comparator.reverseOrder() inverts that ordering, turning the queue into a max-heap.

For a custom type, you can pass a lambda:

PriorityQueue<Task> queue = new PriorityQueue<>((a, b) -> a.priority - b.priority);

This assumes Task has an int priority field. The lambda returns a negative integer, zero, or a positive integer depending on whether a should be ordered before, equal to, or after b. That is the contract of Comparator.compare().

Building a Custom Comparator for Min-Heap or Max-Heap Behavior

The most common use of a comparator is to create a min-heap or max-heap from a type that does not implement Comparable. Suppose you have an event object with a timestamp:

class Event {
    long timestamp;
    String name;
}

To process the earliest event first, you write:

PriorityQueue<Event> queue = new PriorityQueue<>(
    (e1, e2) -> Long.compare(e1.timestamp, e2.timestamp)
);

Long.compare is important. Using subtraction like (int)(e1.timestamp - e2.timestamp) can overflow and produce wrong ordering for large values. Always use the static compare methods for primitive wrappers.

To get the latest event first, reverse the arguments:

PriorityQueue<Event> queue = new PriorityQueue<>(
    (e1, e2) -> Long.compare(e2.timestamp, e1.timestamp)
);

Or use Comparator.comparingLong(Event::getTimestamp).reversed().

Comparing Fields with Comparator.comparing and Chaining

When an object has multiple fields that determine priority, you can chain comparators. For example, a job with both priority and creation time:

PriorityQueue<Job> queue = new PriorityQueue<>(
    Comparator.comparingInt(Job::getPriority)
              .thenComparingLong(Job::getCreatedAt)
);

This orders jobs first by priority, and for equal priorities, by creation time. The chaining is clean and avoids manual if-else logic.

Be careful with Comparator.comparing when the key is nullable. The default behavior throws NullPointerException. Use Comparator.nullsFirst or nullsLast if you expect null keys:

PriorityQueue<Job> queue = new PriorityQueue<>(
    Comparator.comparing(Job::getCategory, Comparator.nullsFirst(String::compareTo))
              .thenComparingInt(Job::getPriority)
);

What Happens When the Comparator Is Inconsistent with equals

Java's PriorityQueue documentation warns that the ordering imposed by a comparator should be consistent with equals. This means compare(a, b) == 0 should imply a.equals(b) is true. If not, the queue will still function, but methods like remove(Object) and contains(Object) may behave unexpectedly.

Consider a comparator that only looks at an ID field:

PriorityQueue<Item> queue = new PriorityQueue<>(
    (a, b) -> a.id - b.id
);

Two different Item objects with the same ID compare as equal. If you call queue.remove(item) with an item that has the same ID but is a different object, the queue may remove the wrong instance because it uses the comparator to locate the element. This is a subtle bug that appears only in certain operations.

If you need identity-based removal, ensure the comparator is consistent with equals, or avoid relying on remove and contains for objects that compare equal but are not equal.

Performance and Runtime Cost of the Comparator

Every offer and poll operation performs O(log n) comparisons. The comparator itself is invoked each time. A cheap comparator, such as one that compares two integers, adds minimal overhead. A comparator that performs expensive calculations, like parsing strings or hitting a database, can dominate the cost of heap operations.

There is no caching of comparison results. The queue does not remember the ordering between two elements; it re-evaluates the comparator whenever needed. This is important if the comparator depends on mutable state. If the state of an element changes after it is inserted, the heap invariant can break. The queue does not re-heapify automatically.

For example, if you insert an object and then change a field that the comparator uses, the queue may no longer be a valid heap. Calling poll() might return an element that is not the true minimum. There is no built-in mechanism to notify the queue of such changes. You must remove and re-insert the element, or design your elements to be immutable with respect to the comparator fields.

Common Mistakes and Edge Cases with PriorityQueue Comparators

One frequent mistake is using subtraction for comparison:

PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> a - b);

This works for small integers but fails for extreme values due to integer overflow. Use Integer.compare(a, b) instead.

Another issue is creating a comparator that is not transitive. For example, a comparator that returns random values or depends on external state violates the comparator contract. This can cause the heap to become corrupted, leading to infinite loops or incorrect ordering.

A third edge case is using a comparator that treats all elements as equal. In that case, the queue behaves like a FIFO list? Actually, it does not guarantee any particular order among equal elements. The heap structure may reorder them arbitrarily, so do not rely on insertion order for equal-priority elements.

Thread-Safety and Concurrent Modification Considerations

PriorityQueue is not thread-safe. If multiple threads modify the queue, you must synchronize externally or use a thread-safe variant like PriorityBlockingQueue. The comparator itself is called from whichever thread performs the operation, so it must be thread-safe if the queue is shared. A stateless comparator that only reads final fields is safe. A comparator that accesses mutable shared state can cause race conditions and inconsistent ordering.

If you need a concurrent priority queue, PriorityBlockingQueue uses the same comparator semantics but adds blocking behavior. The ordering logic is identical; only the concurrency guarantees differ.

When you use a comparator that depends on mutable fields of the elements, concurrent modification of those fields can break the heap even if the queue itself is properly synchronized. The safest design is to make the priority key immutable after insertion.