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 first insert that needs a 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 corrupts the heap.
Reasons about comparator-consistency invariants across the JDK, stability strategies, and the cost rationale for fixing order at construction.
## 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 no-Comparator constructor, the queue uses the element type's `compareTo`. The type must implement `Comparable<E>` (e.g. `Integer`, `String`, `LocalDate`). If it doesn't, the *first comparison* - which usually happens on the second insert - throws `ClassCastException`. 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. ## 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 is now effectively corrupt for that element - remove it before mutating and re-insert, or don't mutate keys of enqueued elements. ## Why construction-time only Reordering on the fly would mean re-heapifying the whole structure; the JDK avoids that by fixing the order up front - one of the reasons inserts stay O(log n).
- 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 and the first element inserts, but the first comparison (typically the second insert) throws ClassCastException because the type can't be cast to Comparable.
saying these in an interview costs you the question
- 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