Java PriorityQueue Max Heap: Using Comparator.reverseOrder()

java priorityqueue max heap requires a clear understanding of the core syntax, runtime behavior, and practical implementation patterns demonstrated in the examples below.

Java's PriorityQueue is a min-heap by default. To use it as a max heap, you must supply a comparator that reverses the natural ordering. This article shows how to do that 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 the ordering. For example, with integers, poll() returns the smallest number.

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.

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:

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, effectively reversing the order. 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.

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 (e.g., 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 must define a total order. 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 try to 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: Find the K largest elements in a stream. Maintain a min-heap of size K, but if you need the largest elements themselves, a max heap can be used with a different strategy.
• 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.

PriorityQueue<String> maxHeapByLength = new PriorityQueue<>(
    (a, b) -> Integer.compare(b.length(), a.length())
);

maxHeapByLength.add("apple");
maxHeapByLength.add("banana");
maxHeapByLength.add("cherry");
System.out.println(maxHeapByLength.poll()); // banana (length 6)

This comparator reverses the natural string ordering 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 rely on equality, not 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.