Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

Java PriorityQueue Max Heap: Using Comparator.reverseOrder()

Learn to use Java's PriorityQueue as a max heap by reversing the default ordering with a comparator, and see practical code examples.

~4 min readJava
#Java#PriorityQueue#Heap#Comparator
Diagram of a Java PriorityQueue configured as a max heap with the largest element at the root.

Java's PriorityQueue is a min-heap by default. To use it as a max heap, supply a comparator that reverses the natural ordering. This article explains how to do that with Comparator.reverseOrder() or a custom comparator, what the runtime characteristics are, and what to watch out for.

The Default Behavior of PriorityQueue

PriorityQueue implements a binary heap that orders elements according to their natural ordering (if they implement Comparable) or by a Comparator provided at construction time. The default constructor creates a min-heap: the head of the queue is the smallest element according to that ordering. For example, with integers, poll() returns the smallest number.

java
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); minHeap.add(5); minHeap.add(2); minHeap.add(8); System.out.println(minHeap.poll()); // 2

This behavior is useful for many algorithms, but sometimes you need the largest element to be served first. That is where a max heap comes in.

Creating a Max Heap with a Comparator

To turn PriorityQueue into a max heap, you need a comparator that reverses the natural order. The simplest way is to use Comparator.reverseOrder() for types that implement Comparable.

java
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); maxHeap.add(5); maxHeap.add(2); maxHeap.add(8); System.out.println(maxHeap.poll()); // 8

For a custom class, you can define your own comparator. Suppose you have a Task class with a priority field:

java
class Task { int priority; String name; // constructor and getters } PriorityQueue<Task> maxHeap = new PriorityQueue<>( (a, b) -> Integer.compare(b.priority, a.priority) );

The comparator (a, b) -> Integer.compare(b.priority, a.priority) returns a negative value when a has a higher priority than b, which makes a come before b in the heap ordering. Because the head is the least element according to the comparator, higher-priority tasks therefore appear at the head. This is equivalent to Comparator.comparing(Task::getPriority).reversed().

Adding and Removing Elements

Once the max heap is configured, the standard PriorityQueue methods work as expected. Use add() or offer() to insert an element, peek() to view the head without removing it, and poll() to retrieve and remove the head.

java
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); maxHeap.offer(10); maxHeap.offer(20); maxHeap.offer(5); System.out.println(maxHeap.peek()); // 20 System.out.println(maxHeap.poll()); // 20 System.out.println(maxHeap.poll()); // 10

The head is always the largest element according to the comparator. After removing the head, the heap rebalances itself so that the next largest element becomes the new head.

Performance Characteristics

PriorityQueue provides O(log n) time for offer() and poll() because both operations may require sifting elements up or down the heap. peek() is O(1) because it simply returns the element at the root. The memory overhead is proportional to the number of elements stored, plus a small constant for the internal array.

There is no significant performance difference between a min-heap and a max-heap when using a comparator; the comparison cost is the only extra factor. For primitive wrappers like Integer, the comparison is cheap. For complex objects, the cost of your comparator dominates the heap operations.

One subtle point: the comparator is used for all internal ordering decisions. If the comparator is inconsistent with equals(), the queue may not behave as expected when removing arbitrary elements (for example, remove(Object)). This is a general contract issue, not specific to max heaps.

Common Pitfalls and Edge Cases

  • Null elements: PriorityQueue does not allow null elements. Attempting to add null throws NullPointerException, regardless of the comparator.
  • Mutable elements: If an element's fields change after insertion, the heap order is not automatically updated. The queue does not re-heapify on mutation. You must remove and re-add the element to restore the heap invariant.
  • Comparator consistency: The comparator should impose a total order for predictable behavior. If it returns 0 for non-equal objects, the heap may treat them as duplicates and the ordering becomes unpredictable.
  • Using natural ordering for non-Comparable objects: If you use new PriorityQueue<>() with a class that does not implement Comparable, you get a ClassCastException at runtime when the first element is added.

When a Max Heap Is the Right Choice

A max heap is useful when you need to repeatedly extract the largest element from a changing collection. Typical use cases include:

  • Top-K problems: To keep the K largest elements in a stream, a min-heap of size K is often used. A max heap is the natural choice when the operation you need is “give me the current largest element.”
  • Scheduling: Process tasks in order of highest priority, where priority is a numeric value.
  • Median finding: Use two heaps (a max heap for the lower half and a min heap for the upper half) to maintain the median efficiently.

For simple cases where the data is static, sorting the collection once may be simpler and faster. But when elements are added and removed over time, a heap gives logarithmic updates instead of linear re-sorting.

Alternative: Using a Custom Comparator for Complex Objects

When your objects do not have a natural order, or you need a different ordering than the one defined by Comparable, you can pass a custom comparator to the constructor. This is the same mechanism used for the max heap, but you can also implement other orderings.

java
PriorityQueue<String> maxHeapByLength = new PriorityQueue<>( (a, b) -> Integer.compare(b.length(), a.length()) ); maxHeapByLength.add("fig"); maxHeapByLength.add("apple"); maxHeapByLength.add("banana"); System.out.println(maxHeapByLength.poll()); // banana (length 6)

This comparator ignores natural string order and instead orders by string length. The same principle applies to any type: define a comparator that returns the desired ordering, and PriorityQueue will maintain the heap accordingly.

Remember that the comparator must be consistent with equals() if you plan to use remove() or contains(). If not, these methods may fail to find elements even when they are present, because they use equals() rather than the comparator.

For most max-heap use cases, Comparator.reverseOrder() is sufficient for built-in types. For custom types, a lambda or method reference gives you full control without extra boilerplate.

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.