PriorityQueue — Heap Structure and Use Cases
Fast recall
Quick revision
Core answer
Understanding of heap-based priority structures, time complexity, and common algorithmic patterns (top-K, Dijkstra, scheduling)
Assuming PriorityQueue iterates in sorted order — iteration is NOT guaranteed to be in priority order. Only poll() and peek() respect priority.
Mention that PriorityQueue is a min-heap by default, so for a max-heap use Collections.reverseOrder() or a negated Comparator. Also mention it is not thread-safe; use PriorityBlockingQueue for concurrent use.
Interview-ready guide
Interview answer
PriorityQueue is a binary min-heap stored in a flat array — the most important thing to know is that iterating over it does NOT give sorted order.
How it works:
- Heap property: root (index 0) is always the minimum; siblings have no ordering relationship
peek()is O(1) — returns index 0;offer()/poll()are O(log n) — sift up/down to restore heap propertyremove(Object)is O(n) — requires a linear scan
Ordering:
- Default: min-heap; for max-heap pass
Comparator.reverseOrder()to the constructor - Custom objects: implement
Comparableor pass aComparator— without one, you getClassCastExceptionat runtime (not compile time)
Top-K pattern:
- Maintain a min-heap of size K; each element larger than the root replaces it
- O(n log K) instead of O(n log n) for a full sort — the classic interview optimization
I recommend PriorityQueue for priority-based extraction patterns and PriorityBlockingQueue for concurrent producer-consumer scenarios.
PriorityQueue — Heap Structure and Use Cases
Direct Answer
PriorityQueue is backed by a binary min-heap stored in an array. peek() and poll() return the smallest element in O(1) and O(log n) respectively. It is ideal for top-K problems, Dijkstra's algorithm, task scheduling, and any pattern requiring repeated minimum extraction.
Deep Dive & Architecture
compute, merge, computeIfAbsent, and computeIfPresent are Map methods (Java 8+) that atomically combine get + check + put into a single operation, replacing the verbose get-check-put anti-pattern. computeIfAbsent(key, mappingFunction) — if key absent, compute value and put; most-used for lazy initialization of multi-valued maps: map.computeIfAbsent(key, k -> new ArrayList<>()).add(value). computeIfPresent(key, remappingFunction) — if key present, recompute value (or remove if null returned). compute(key, remappingFunction) — recompute regardless of presence (function gets old value or null). merge(key, value, remappingFunction) — if absent, put value; if present, apply function to combine: map.merge(word, 1, Integer::sum) is the idiomatic word-counter. Why they matter: (1) atomic in ConcurrentHashMap — no lost updates from concurrent get-check-put races; (2) less code than if (map.containsKey(k)) map.put(k, ...) else map.put(k, ...); (3) cleaner intent — the operation says what it does. Pitfalls: (1) not atomic in non-concurrent maps (HashMap) — only the API is single-call, not thread-safe; (2) returning null from a remapping function removes the key — surprising; (3) don't recursively modify the map inside the function — undefined behavior; (4) merge doesn't handle null values the same way as compute — read the Javadoc. For interviews: lead with 'replaces get-check-put, atomic in ConcurrentHashMap, idiomatic for multimap lazy-init and counters'.
PriorityQueue is backed by a binary min-heap stored in an array. peek() and poll() return the smallest element in O(1) and O(log n) respectively. It is ideal for top-K problems, Dijkstra's algorithm, task scheduling, and any pattern requiring repeated minimum extraction.
A common mistake is confusing the interface with the implementation (e.g., saying List when you mean ArrayList), or not knowing that Map does not extend Collection.
Common Mistakes & Pitfalls
Assuming PriorityQueue iterates in sorted order — iteration is NOT guaranteed to be in priority order. Only poll() and peek() respect priority.
Check your understanding
Answer these without looking back at the article.
- What is the Java Collections Framework (JCF) and why does it exist? It provides a unified architecture of interfaces and implementations for storing and manipulating groups of objects, replacing the ad-hoc pre-JCF classes (Vector, Hashtable, Enumeration) with a consistent, interoperable API.
- How does HashSet work internally in Java?
- How does HashMap internally handle hash collisions in Java 8+? Explain the transition from linked list to tree.
Related interview prep categories
1Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.