How do you control PriorityQueue ordering (e.g. build a max-heap or order by an object field), and what must the Comparator guarantee?
answer
- No comparator => natural order => element must be Comparable
- reverseOrder() = max-heap
- comparingInt(field) (+ reversed/thenComparing) for objects
- Comparator needs total order: transitive, sign-consistent
- Equal priority isn't FIFO - add a sequence tie-breaker
basics
~10 sPass a Comparator to the constructor: PriorityQueue<>(Comparator.reverseOrder()) for a max-heap, or Comparator.comparingInt(Task::getPriority) to order by a field. Without one it uses the element's natural ordering, so the type must be Comparable.
solid answer
~50 sOrdering is set once at construction. With no Comparator, the queue uses the elements' natural ordering, so the element type must implement Comparable or you'll get a ClassCastException on the very first offer or add, because the element is cast before any comparison. To customize, pass a Comparator: Comparator.reverseOrder() turns the default min-heap into a max-heap; Comparator.comparingInt(Task::priority) orders by a field; you can chain with thenComparing for tie-breaks and reversed() to flip. The Comparator must impose a total order consistent with the contract - it must be transitive and antisymmetric, and return 0 only for elements you genuinely consider equal-priority. Two elements that compare equal (0) come out in unspecified relative order - PriorityQueue is not stable - so add an explicit tie-breaker (e.g. insertion sequence) if FIFO-among-equals matters. The ordering is fixed for the queue's life; you can't swap Comparators later.
go deeper
Knows you can pass a Comparator and that reverseOrder() makes a max-heap.
Builds field-based and reversed comparators, knows natural order requires Comparable, and that equal priorities aren't FIFO.
States the total-order contract, avoids overflow-prone subtraction, adds sequence tie-breakers, and knows mutating enqueued keys can corrupt the heap.
Reasons about comparator-consistency invariants across the JDK, stability strategies, and the cost of rebuilding the heap when an ordering must change.
## Two ways to define order A `PriorityQueue` needs to know how to compare any two elements to decide which has higher priority (comes out first). There are exactly two sources, chosen at **construction time**: 1. **Natural ordering** - if you call a constructor with no Comparator and no sorted source, the queue uses the element type's `compareTo`. The type must implement `Comparable` (e.g. `Integer`, `String`, `LocalDate`). If it doesn't, the *first* `offer` or `add` throws `ClassCastException`, even on an empty queue with nothing to compare against, because `siftUpComparable` casts the element before its loop (the same on JDK 27 and 25). The bulk constructor differs: a one-element list needs no sift and succeeds, and a two-element list throws. Natural order is a **min-heap**: smaller `compareTo` => higher priority => out first. 2. **A Comparator** - pass one to the constructor: `new PriorityQueue<>(comparator)`. This fully overrides natural ordering. The copy constructors take neither: `new PriorityQueue<>(sortedSet)` and `new PriorityQueue<>(otherQueue)` inherit the source's ordering, so a queue built from a reverse-ordered `TreeSet` is still a max-heap. ## Common Comparator recipes ``` // Max-heap of integers (largest out first): new PriorityQueue<>(Comparator.reverseOrder()); // Order Tasks by an int field, smallest priority first: new PriorityQueue<>(Comparator.comparingInt(Task::priority)); // Largest field first (max-heap by field): new PriorityQueue<>(Comparator.comparingInt(Task::priority).reversed()); // Primary by priority, tie-break by arrival time: new PriorityQueue<>(Comparator.comparingInt(Task::priority) .thenComparingLong(Task::arrival)); ``` `Comparator.comparing`/`comparingInt` extract a sort key; `reversed()` flips direction; `thenComparing` adds tie-breakers. ## The contract a Comparator must honor A `Comparator<T>.compare(a,b)` returns a negative number if `a` should come out before `b`, positive if after, and `0` if they're equal-priority. To be a valid ordering it must impose a **total order**: - **Antisymmetric / sign-consistent**: `sgn(compare(a,b)) == -sgn(compare(b,a))`. - **Transitive**: if `a<b` and `b<c` then `a<c`. - **Consistent equality**: if `compare(a,b)==0`, then for any `c`, `compare(a,c)` and `compare(b,c)` agree. Violating these (a common bug: `return a.value - b.value` on ints that can overflow, or a comparator that isn't transitive) gives undefined, sometimes silently wrong, behavior. Prefer `Integer.compare(a,b)` / `comparingInt` over hand subtraction to avoid integer overflow. ## Equal priority is *not* stable If two elements compare as `0`, the heap makes **no promise** about which comes out first - PriorityQueue is **not a stable/FIFO** queue among equals. If you need FIFO among equal priorities (very common in schedulers), add a monotonically increasing **sequence number** as a tie-breaker in the Comparator. ## Order is fixed for life The Comparator (or the natural-order choice) is captured at construction and **cannot be changed** afterward, nor recomputed if an element's fields mutate. If a key field of an element changes *after* insertion, the heap is **not** automatically re-ordered and can be left effectively corrupt for that element - remove it before mutating and re-insert, or don't mutate keys of enqueued elements. ## Changing the order means a new queue The `comparator` field is `private final` and the class has no setter. A different ordering would invalidate the whole heap, so build a new queue with `new PriorityQueue<>(newOrder)` and `addAll` the old one into it.
- You need a scheduler where equal-priority tasks run FIFO. How?Add a tie-breaker on an ever-increasing sequence number: Comparator.comparingInt(Task::priority).thenComparingLong(Task::seq). The seq makes the order total and stable among equal priorities.
- What happens if you put a non-Comparable type in a PriorityQueue with no Comparator?Construction succeeds, but the first offer or add throws ClassCastException, because the element is cast to Comparable before any comparison. The class Javadoc says this "may result" in the exception and offer lists it for an element that cannot be compared, but neither promises the first-insert timing; that is OpenJDK's code, the same at JDK 27 and 25.
- Using a non-Comparable type with no Comparator (ClassCastException at runtime)
- Assuming equal-priority elements come out in insertion order
- Writing a-b subtraction comparators that can integer-overflow
- Mutating an enqueued element's ordering field and expecting the queue to re-sort
- Thinking you can change the Comparator after construction
- PriorityQueue(Comparator) constructor
- Java 1.8
- Comparator.comparing, reversed and thenComparing
- Java 1.8
Assumes JDK 27. The first-offer ClassCastException comes from private code rather than the API contract, and PriorityQueue.java is identical at JDK 25, where the result is the same.
context
- PriorityQueue (Java SE 27 & JDK 27)docs.oracle.com
- Comparator (Java SE 27 & JDK 27)docs.oracle.com
- PriorityQueue.java at jdk-27-gagithub.com