What are the thread-safety and mutable-key pitfalls of PriorityQueue, and how do you address them?
answer
- No internal locking -> concurrent use corrupts the heap
- PriorityBlockingQueue for threads; take() blocks
- Ordering key must be immutable while enqueued
- Mutating a key after insert => wrong poll, contains may miss it
- Change priority via remove+reinsert or lazy stale entries
basics
~20 sPriorityQueue 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 breaks.
solid answer
~40 sPriorityQueue 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 position is computed only at insertion; 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 return wrong results and even contains can fail to find it. If a priority must change, remove the element first, mutate it, then re-insert. PriorityBlockingQueue's iterator is also unordered and weakly consistent, same as the non-blocking one.
go deeper
Knows PriorityQueue isn't thread-safe and there's a blocking version for concurrency.
Chooses PriorityBlockingQueue vs locking and knows not to mutate ordering fields after insert.
Explains how concurrent sift operations corrupt the heap, the immutable-key invariant, and remove-and-reinsert vs lazy-deletion to change priority.
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** swaps. 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 duplicated, the head may no longer be the minimum, indices can go out of bounds, or you get `ConcurrentModificationException`/`ArrayIndexOutOfBoundsException`. 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. (There is no `Collections.synchronizedQueue` returning a priority-aware wrapper that you'd want here; explicit locking or PriorityBlockingQueue is the answer.) Note: even with `PriorityBlockingQueue`, its **iterator is still unordered and weakly consistent** - same iteration caveat as the non-blocking version; only `poll`/`take` 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 swaps 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, and contains(task) // may even fail because the search path assumes heap order. ``` The invariant **"keys used for ordering must not change while the element is in the queue"** is required for the heap to stay valid. 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. These are explicit parts of the contract, not bugs. ## 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? -> still must drain/poll; 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.
saying these in an interview costs you the question
- 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