PriorityQueue: Next-Best Without Sorting the Whole List

A pack station has fifty open orders. You sort the ArrayList after every arrival so index 0 is the smallest ticket. That is correct about “who is next” and dishonest about the bill: you reordered everything to answer one question.

PriorityQueue keeps the next-best element at the root of a heap in O(log n) per offer and poll. It implements Queue and is not FIFO. The heap layout post owns sift diagrams and parent-index formulas. This post is the JDK type: comparator versus natural order, why the iterator is unsorted, and why changing priority is remove then add.

Next-best is not first-in

Queue.offer / Queue.poll on an ArrayDeque mean arrival order. The same method names on a PriorityQueue mean comparator order (or natural order). The interface compiled. The contract did not stay FIFO.

Queue<Order> byTotal = new PriorityQueue<>(Comparator.comparing(Order::total));
byTotal.offer(order("o-100", "SKU-1", "19.99"));
byTotal.offer(order("o-101", "SKU-2", "5.00"));
byTotal.offer(order("o-102", "SKU-3", "12.00"));

Order next = byTotal.poll(); // o-101 — smallest total, not o-100

If a method parameter is Queue<Order> and the caller needed the oldest pick, a PriorityQueue argument is a bug that type-checks. Prefer Deque for FIFO. Prefer PriorityQueue when the sentence is “who is best now as the set mutates.”

You meant	Type
Next arrived	`ArrayDeque` as a `Queue`
Next-best by a field	`PriorityQueue` + `Comparator`
Entire collection in order, staying sorted	`TreeSet` / `TreeMap` — Navigable Collections
Next-best and another thread waits	`PriorityBlockingQueue` — BlockingQueue

PriorityQueue is unbounded. offer does not return false for space. It is not thread-safe. It forbids null. It is not a List and not a SequencedCollection: there is no honest first-to-last encounter order, only a heap.

Binary heap, not a sorted list

Decision internals at the level you need to pick the class. A binary heap is a complete tree stored in an array. The minimum (by the comparator) sits at index 0. Every parent is less than or equal to its children. The rest of the array is not sorted.

Min-heap of totals: 5.00, 19.99, 12.00, 8.50

        5.00
       /    \
   8.50     12.00
   /
19.99

Array: [5.00, 8.50, 12.00, 19.99]   // one legal heap, not "sorted orders"

offer appends at the next free slot and sifts up. poll takes index 0, moves the last element into the root, and sifts down. peek reads index 0 and does not sift. Layout, sift code, and why heapify is O(n) live on Heaps. This series does not re-teach heapsort.

Method	Heap job	Cost
`offer` / `add`	append + sift up	`O(log n)`
`poll` / `remove()`	take root, sift down	`O(log n)`
`peek` / `element`	read root	`O(1)`
`remove(Object)` / `contains`	scan, then maybe sift	`O(n)`
`iterator()`	heap order on the array	not sorted

Duplicates are allowed. Equal priorities have no promised order. If “same total, older id first” matters, put a tie-breaker in the comparator — thenComparing(Order::id) — not a hope that the heap is stable.

Peek is cheap because the extreme is already at the root. Sorting the other elements would be a different type.

Comparator or Comparable

No comparator means natural order: elements must implement Comparable, and the queue is a min-heap of that order. Order in this series is a record without Comparable. Passing it to new PriorityQueue<>() throws ClassCastException on the second insert, when the heap first compares.

PriorityQueue<Order> broken = new PriorityQueue<>();
broken.offer(order("o-100", "SKU-1", "19.99"));
broken.offer(order("o-101", "SKU-2", "5.00")); // ClassCastException

Give it a Comparator. Min-heap on total, or a max-heap with .reversed():

Comparator<Order> smallestFirst = Comparator
        .comparing(Order::total)
        .thenComparing(Order::id);

Comparator<Order> largestFirst = smallestFirst.reversed();

PriorityQueue<Order> packSmall = new PriorityQueue<>(smallestFirst);
PriorityQueue<Order> packLarge = new PriorityQueue<>(largestFirst);

Integer, String, and BigDecimal already implement Comparable. new PriorityQueue<BigDecimal>() is a min-heap of totals without a lambda. Domain records should still get an explicit comparator so the next reader does not guess which field is “natural.”

PriorityQueue<BigDecimal> totals = new PriorityQueue<>();
totals.offer(new BigDecimal("19.99"));
totals.offer(new BigDecimal("5.00"));
totals.peek(); // 5.00

A collection of Comparable values can be heapified in O(n) with the collection constructor. Order is not Comparable, so that constructor is the wrong one — it will throw on the first compare. Build with the comparator, then addAll:

PriorityQueue<Order> pending = new PriorityQueue<>(smallestFirst);
pending.addAll(List.of(
        order("o-100", "SKU-1", "19.99"),
        order("o-101", "SKU-2", "5.00"),
        order("o-102", "SKU-3", "12.00")));

Note: The comparator must be consistent with equals if you rely on remove(Object) to find the same order you offered. Records already equal on all components. A comparator that only looks at total can consider two different ids “equal in priority” while equals says they are different — that is fine for poll order, and remove still uses equals. Do not mutate an element after it is in the heap; the record is immutable, which is why this series uses records.

Lab: rush picks by total

Same checkout records. Smallest active total ships first so the station clears cheap tickets. A rush upgrade replaces the order: new total, same id.

public record Order(
        String id,
        String customerEmail,
        List<LineItem> items,
        BigDecimal total,
        boolean active) {}

public record LineItem(String sku, int quantity, BigDecimal unitPrice) {}

static Order order(String id, String sku, String total) {
    BigDecimal price = new BigDecimal(total);
    return new Order(
            id,
            id + "@ex.com",
            List.of(new LineItem(sku, 1, price)),
            price,
            true);
}

Helper plus comparator, then three offers:

Comparator<Order> smallestFirst = Comparator
        .comparing(Order::total)
        .thenComparing(Order::id);

PriorityQueue<Order> pending = new PriorityQueue<>(smallestFirst);
Order o100 = order("o-100", "SKU-1", "19.99");
Order o101 = order("o-101", "SKU-2", "5.00");
Order o102 = order("o-102", "SKU-3", "12.00");
pending.offer(o100);
pending.offer(o101);
pending.offer(o102);

Order first = pending.peek(); // o-101 (5.00)

PriorityQueue<Order> largestFirst = new PriorityQueue<>(smallestFirst.reversed());
largestFirst.addAll(List.of(o100, o101, o102));
largestFirst.peek(); // o-100 (19.99) — max-heap, same class

Print what the iterator claims versus what poll claims:

List<String> fromIterator = new ArrayList<>();
for (Order o : pending) {
    fromIterator.add(o.id() + "=" + o.total());
}

List<String> fromPoll = new ArrayList<>();
PriorityQueue<Order> drain = new PriorityQueue<>(pending);
while (!drain.isEmpty()) {
    Order o = drain.poll();
    fromPoll.add(o.id() + "=" + o.total());
}

Typical result — iterator follows the heap array, drain follows priority:

iterator:  o-101=5.00, o-100=19.99, o-102=12.00   (heap-shaped, not sorted)
poll:      o-101=5.00, o-102=12.00, o-100=19.99   (actual next-best sequence)

Your iterator line may differ; any heap-shaped permutation of the three is legal. The poll line is the contract. Do not sort a UI table by iterating a PriorityQueue. Drain a copy with poll, or use a sorted collection.

toArray() is the same trap: it dumps the heap array, not a sorted report.

Object[] snapshot = pending.toArray(); // heap order, not totals ascending

Changing priority is remove then add

There is no decreaseKey on PriorityQueue. The heap does not track “where did o-100 go” in O(1). To change an order’s total you remove the old instance (O(n) scan) and offer the new one (O(log n)).

Order upgraded = new Order(
        o100.id(),
        o100.customerEmail(),
        o100.items(),
        new BigDecimal("3.00"),
        true);

boolean found = pending.remove(o100); // O(n), uses Order.equals
pending.offer(upgraded);              // O(log n) sift

Order nowFirst = pending.peek();      // upgraded o-100 if 3.00 is the min

If remove returns false, the old record was not in the heap — wrong instance, or you already polled it. Because Order equality includes total, you must remove the object you offered, not a newly built record with the same id and a different total.

A map from id → Order beside the queue makes “find by id” honest. The queue still cannot update in place: take the mapped instance, remove it, offer the replacement, update the map. Frequent decrease-key is a different algorithm; the heap post names Fibonacci heaps as literacy, not as a class you should write.

Map<String, Order> byId = new HashMap<>();
byId.put(o100.id(), o100);
pending.offer(o100);

Order updated = new Order(
        o100.id(), o100.customerEmail(), o100.items(),
        new BigDecimal("3.00"), true);
pending.remove(byId.get("o-100"));
pending.offer(updated);
byId.put("o-100", updated);

Equal totals need an explicit tie-breaker if “earlier id first” is a business rule. The heap will not remember arrival order among equals.

record Ranked(int seq, Order order) {}

int seq = 0;
PriorityQueue<Ranked> stable = new PriorityQueue<>(
        Comparator.comparing((Ranked r) -> r.order().total())
                .thenComparingInt(Ranked::seq));
stable.offer(new Ranked(seq++, o100));
stable.offer(new Ranked(seq++, order("o-103", "SKU-9", "19.99")));
// same total as o-100: o-100 still polls first because seq is smaller

When not PriorityQueue

You needed FIFO. Same priority, arrival order: ArrayDeque. PriorityQueue will not preserve insertion order among equals unless you add a sequence number to the comparator.
You needed a sorted scan. Walk every key in order, leave the collection intact: TreeSet / TreeMap, or sort a copy. Polling a heap to print a report empties it and costs O(n log n) — that is sorting, not “using a priority queue.”
You needed indexes. Not a List. Copy to a list if a caller demands one, knowing the copy is a snapshot.
Another thread waits on empty/full. PriorityBlockingQueue is the concurrent cousin. It is still a heap, still not FIFO. Details stay in BlockingQueue. Collections.synchronizedCollection around a PriorityQueue does not wait.
null elements. Forbidden (NullPointerException). Empty is poll() == null.
The list is tiny and already sorted for a UI. Twenty rows: sort once. Do not invent a heap for a dropdown.

PriorityQueue is fail-fast and single-threaded in java.util. Iterator contracts are on the roadmap.

Interview lens

Interviewers want “heap, not sorted, not FIFO,” plus the three costs.

Complexity they expect. offer / add: O(log n). poll / remove(): O(log n). peek: O(1). remove(Object) / contains: O(n). Building from a collection: O(n) heapify, not n times O(log n) if you use the collection constructor.

What to draw. A small complete tree, array underneath [min, …], arrows for sift up on insert and sift down on poll. Write “iterator ≠ this order.” Cross out ArrayDeque FIFO and Collections.sort on every insert. Label Comparator on the edge, not inside Order unless it is Comparable.

Typical questions:

Question	Honest answer
Is `PriorityQueue` sorted?	No. It is a heap. Only the root is the extreme.
Time of `offer` / `poll` / `peek`?	`O(log n)`, `O(log n)`, `O(1)`.
Why is the iterator unordered?	It walks the heap array. Heap-order is not sorted order.
Natural order vs `Comparator`?	No comparator → `Comparable` min-heap. Otherwise the comparator defines “best.” `reversed()` is a max-heap.
It implements `Queue` — is it FIFO?	No. Poll is next-best, not first-in.
How do you change priority?	`remove` + `offer`. No decrease-key. `remove` is `O(n)`.
Thread-safe?	No. `PriorityBlockingQueue` for blocking concurrent use.
`null`?	Forbidden. `poll` returns `null` only when empty.

Wrong answer: “PriorityQueue keeps elements in sorted order so iterating is sorted.” Iterating is heap order. Drain with poll if you need best-to-worst, and know that empties the queue.

Cheat sheet

Type        PriorityQueue — Queue, not List, not FIFO, not SequencedCollection
Layout      binary heap in an array; min at index 0 (comparator order)
offer/add   O(log n) sift up
poll        O(log n) sift down
peek        O(1) root
remove(o)   O(n) scan
Iterator    NOT sorted — do not use it as a report order
Comparator  required unless E is Comparable; reversed() = max-heap
Tie-break   thenComparing(...) ; heap is not stable
Priority    change = remove + offer ; no decrease-key
Nulls       forbidden
Threads     not safe; PriorityBlockingQueue is the waiting cousin
Vs FIFO     ArrayDeque
Vs sorted   TreeSet / TreeMap (navigable post)
Vs layout   ds-heap for sift pictures; this post is the JDK type

Do:

Name the hot operation: next-best as items arrive and leave.
Pass an explicit Comparator on Order fields; add a tie-breaker when equals in priority must still be deterministic.
Drain with poll (on a copy) when you need priority order as a sequence.

Don’t:

Sort the whole list on every insert to keep index 0 honest.
Trust for (Order o : queue) as sorted.
Treat Queue in a signature as a FIFO promise.

Wrap-up

PriorityQueue is a binary heap behind the Queue methods. poll is the next-best element by Comparator or Comparable, not the first inserted. The iterator is unordered on purpose. Changing a priority is a linear remove plus a logarithmic offer. For FIFO use ArrayDeque. For a living sorted view use a navigable map or set. For a waiting concurrent heap use PriorityBlockingQueue and keep the blocking details on that post.

Sorted keys with ceiling and floor are the next contract when “who is next” is not enough and you need the whole order.

Next optional step in the series When you need sorted keys, ceiling and floor, and an honest Comparator. Navigable Collections: TreeSet, TreeMap, and the Comparator Contract

PriorityQueue:Next-Best Without Sorting the Whole List

Next-best is not first-in

Binary heap, not a sorted list

Comparator or Comparable

Lab: rush picks by total

Changing priority is remove then add

When not PriorityQueue

Interview lens

Cheat sheet

Wrap-up

Pick the Collection:Nulls, Order, Threads, and the Hot Operation

Sequenced Collections:First, Last, and Reversed Without the Ceremony

Stream Gatherers:Custom Intermediate Ops Without Breaking the Pipeline

Java Streams:Filter, Map, and Collect Without the Nested Loop Soup

Next-best is not first-in

Binary heap, not a sorted list

Comparator or Comparable

Lab: rush picks by total

Changing priority is remove then add

When not PriorityQueue

Interview lens

Cheat sheet

Wrap-up

Related posts

Pick the Collection:Nulls, Order, Threads, and the Hot Operation

Sequenced Collections:First, Last, and Reversed Without the Ceremony

Stream Gatherers:Custom Intermediate Ops Without Breaking the Pipeline

Java Streams:Filter, Map, and Collect Without the Nested Loop Soup