Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

Java PriorityQueue Comparator: Control Ordering

Use a Comparator with Java PriorityQueue to control ordering, including min-heap, max-heap, and field-based priority rules.

~5 min readJava
#PriorityQueue#Comparator#Java Collections#Heap
Illustration of a Java PriorityQueue heap structure with a comparator knob controlling element 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. Passing a Comparator to the PriorityQueue constructor lets you define exactly how elements are prioritized without changing the element class itself.

In the two-argument constructor, the comparator is the second argument. The queue uses it to determine the relative priority of any two elements. That ordering decides which element is returned by peek() and removed by poll().

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:

java
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:

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

This assumes Task has an accessible 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:

java
class Event { long timestamp; String name; }

To process the earliest event first, you write:

java
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. Use static comparison methods such as Long.compare and Integer.compare instead of subtraction.

To get the latest event first, reverse the arguments:

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

Or use Comparator.comparingLong(e -> e.timestamp).reversed().

Comparing Fields with Comparator.comparing and Chaining

When an object has multiple fields that determine priority, you can chain comparators. For example, assuming Job exposes getters for priority and creation time:

java
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 mapped key can be null. The default behavior throws NullPointerException. Use Comparator.nullsFirst or nullsLast if you expect null keys:

java
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 collection documentation recommends that the ordering imposed by a comparator 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:

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

Two different Item objects with the same ID compare as equal under this comparator, but equals may still treat them as different. remove(Object) and contains(Object) find elements using equals, not the comparator, so passing a different object with the same ID to remove will not remove the stored item. The inconsistency can also make code that relies on equality-based checks harder to reason about.

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:

java
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 incorrect ordering or non-termination.

A third edge case is using a comparator that treats all elements as equal. The queue 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.

Try matching browser tools

All tools

Small utilities that fit Java work — they run entirely in this browser tab, so nothing you paste leaves your device.

All Java guides

More in Java

All Java guides

The guides filed next to this one in Java, in library order.