skip to content

What are the thread-safety and mutable-key pitfalls of PriorityQueue, and how do you address them?

level: seniorimportance: should knowfreq 40%

answer

  1. No internal locking -> concurrent use corrupts the heap
  2. PriorityBlockingQueue for threads; take() blocks
  3. Ordering key must be immutable while enqueued
  4. Mutated key: poll can go wrong; linear contains unaffected
  5. Change priority via remove+reinsert or lazy stale entries

basics

~20 s

PriorityQueue is not thread-safe - concurrent use can corrupt it, so use PriorityBlockingQueue or external locking. Also, if you change a field used for ordering after inserting an element, the queue won't re-sort and its order can break.

solid answer

~50 s

PriorityQueue has no internal synchronization, so concurrent inserts/polls from multiple threads can interleave during sift-up/sift-down and corrupt the heap (lost elements, wrong head, exceptions). For concurrent producers/consumers use java.util.concurrent.PriorityBlockingQueue, which is thread-safe and blocks on take() when empty, or guard a plain PriorityQueue with explicit locking. The second, subtler pitfall: ordering keys must be effectively immutable while an element is enqueued. The heap compares an element only when a sift touches it; if you mutate a field the Comparator uses afterward, the heap is not re-ordered and that element can sit in the wrong place, so peek/poll can return wrong results. contains still finds it, because it scans the whole array with equals. If a priority must change, remove the element first, mutate it, then re-insert. PriorityBlockingQueue's iterator is unordered too, and weakly consistent where PriorityQueue's is fail-fast.

go deeper

for a junior

Knows PriorityQueue isn't thread-safe and there's a blocking version for concurrency.

for a middle

Chooses PriorityBlockingQueue vs locking and knows not to mutate ordering fields after insert.

for a senior

Explains how concurrent sift operations corrupt the heap, the immutable-key invariant, and remove-and-reinsert vs lazy-deletion to change priority.

for a principal

Weighs lock contention of PriorityBlockingQueue, designs decrease-key strategies for graph algorithms, and reasons about visibility/contract trade-offs in the API design.

## Pitfall 1: it is not thread-safe `PriorityQueue` does **no internal locking**. Its mutating operations (`offer`, `poll`, `remove`) restructure a shared array via multi-step **sift-up / sift-down** moves. If two threads run these concurrently (or one mutates while another iterates), the steps interleave and leave the array in an **inconsistent state**: elements can be lost or returned twice, the head may no longer be the minimum, and you can get `NullPointerException` from a null slot, `ArrayIndexOutOfBoundsException` when racing pollers drive `size` below zero, or `ConcurrentModificationException` from an iterator. Run four threads polling one queue on JDK 27 and some elements come back twice. There's no guarantee of visibility of one thread's writes to another either. **Fixes:** - **`java.util.concurrent.PriorityBlockingQueue`** - a thread-safe, unbounded priority queue. It synchronizes internally (a lock), and `take()` **blocks** until an element is available, `put()` never blocks (unbounded). Ideal for producer/consumer pipelines where consumers want the highest-priority item next. - Or wrap a plain `PriorityQueue` in your own lock and do all access under it. (`Collections` has no `synchronizedQueue`, and `Collections.synchronizedCollection(pq)` returns a plain `Collection` with no `poll` or `peek`, so explicit locking or PriorityBlockingQueue is the answer.) Note: even with `PriorityBlockingQueue`, its **iterator is still unordered** - same iteration caveat as the non-blocking version - and it is **weakly consistent**, where `PriorityQueue`'s iterator throws `ConcurrentModificationException` when it detects a change. `poll`, `take` and `drainTo` give priority order. ## Pitfall 2: mutable ordering keys The heap decides where to put an element by comparing it **at insertion time** and during the sifts triggered by other inserts/polls. It does **not** observe later field changes. So if your element's priority is derived from a mutable field: ``` pq.offer(task); // ordered by task.priority == 5 task.setPriority(1); // changed AFTER insertion // the heap was NOT re-ordered: this task may be deep in the heap, // so poll() can return a 'worse' task first. contains(task) still // returns true: it scans the whole array with equals, not heap order. ``` On JDK 27, three tasks at 5, 7 and 9 poll as 5, 1, 7 after the 9 is changed to 1. A `contains` miss would need an `equals` that reads the changed field, plus a lookup with a separate object holding the old value. The invariant **keys used for ordering must not change while the element is in the queue** is what guarantees the heap stays valid, although `PriorityQueue`'s Javadoc does not spell it out. A change that still fits the element's position does no harm, which is how this bug can stay hidden. If a priority genuinely must change (e.g. Dijkstra's decrease-key), you must: 1. `remove(element)` (O(n)) to take it out, **then** mutate, **then** `offer` it again; or 2. use the **lazy / stale-entry** pattern - leave the old entry, insert a new one with the new priority, and skip stale entries when you poll them. This avoids the O(n) remove and is the common idiom in graph algorithms. ## Why the JDK works this way Adding synchronization to every op would slow the single-threaded common case, and re-validating order on every field read is impossible (the queue can't observe arbitrary mutations). So the JDK pushes both concerns to the caller: pick a concurrent variant when you share across threads, and treat ordering keys as immutable-while-enqueued. The Javadoc states the threading rule outright ("this implementation is not synchronized"); the key rule follows from the heap invariant. Neither is a bug. ## Quick checklist - Shared across threads? -> `PriorityBlockingQueue` or explicit lock. - Priority derived from a field that changes? -> remove-then-reinsert, or lazy stale entries. - Need ordered iteration concurrently? -> drain, or sort `toArray()`; the iterator is unordered either way.

  • Which JDK class gives a thread-safe priority queue and how do its take/put differ?
    PriorityBlockingQueue. take() blocks until an element is available; put()/offer() never block because it's unbounded. Iteration is still unordered/weakly consistent.
  • You must lower an element's priority while it's in the queue. What do you do?
    Either remove it (O(n)), mutate, then re-offer; or use the lazy pattern: insert a new entry with the lower priority and skip the stale higher-priority entry when polled.

  • Sharing a plain PriorityQueue across threads without locking
  • Assuming Collections.synchronizedCollection gives priority-correct concurrency
  • Mutating an element's ordering field while it's enqueued and expecting re-sort
  • Thinking PriorityBlockingQueue's iterator returns elements in order

java.util.concurrent.PriorityBlockingQueue
Java 1.5

context