What is a PriorityQueue in Java and how do you get elements out in priority order?
answer
- Min-heap by default: smallest out first
- Natural order OR a Comparator
- poll removes head, peek looks
- poll/peek return null; remove/element throw
- No nulls, not thread-safe, unbounded
basics
~20 sA PriorityQueue is a queue where the smallest element (by natural order or a Comparator) always comes out first. You add with offer/add and remove the highest-priority element with poll. peek looks at the head without removing it.
solid answer
~40 sPriorityQueue is a Queue implementation backed by a binary heap. Instead of FIFO, the element at the head is always the one with the highest priority - by default the smallest by natural ordering, or by a Comparator you pass to the constructor. You enqueue with offer (or add) and dequeue the highest-priority element with poll, which returns and removes the head; peek returns it without removing. poll/peek return null when empty (unlike remove/element, which throw). It is unbounded and grows automatically, is not thread-safe (use PriorityBlockingQueue for concurrency), and does not permit null elements. Typical uses: scheduling, Dijkstra's shortest path, top-K, and merging sorted streams - anywhere you repeatedly need the current minimum or maximum.
go deeper
Knows it returns the smallest first by default, uses offer/poll/peek, and that it isn't FIFO.
Distinguishes natural order vs Comparator, builds a max-queue, knows the null/throws vs null-return behavior and no-null rule.
Explains the heap backing, thread-safety (PriorityBlockingQueue), comparator consistency, and chooses it for greedy/top-K problems.
Reasons about comparator stability, memory/resize cost, alternatives (TreeSet, indexed heaps for decrease-key) and API contract guarantees across the JDK.
## What problem it solves An ordinary queue is **FIFO** (first-in, first-out): the order you take things out matches the order you put them in. Sometimes you instead want to always pull out the *most important* item next, regardless of when it arrived - e.g. the next task to run, the closest node to explore. A **priority queue** does exactly this: each element has a **priority**, and the *dequeue* operation always returns the element with the best priority. ## What "priority" means here Java's `java.util.PriorityQueue<E>` is a **min-priority queue by default**: the element that is *smallest* according to ordering is the one returned first. "Smallest" is decided one of two ways: - **Natural ordering** - the element type implements `Comparable<E>` (e.g. `Integer`, `String`), so the JDK can call `a.compareTo(b)`. - **A `Comparator`** you pass to the constructor: `new PriorityQueue<>(comparator)`. This overrides natural order and lets you do anything, including a *max*-queue with `Comparator.reverseOrder()`. ## The core operations - `offer(e)` / `add(e)` - insert an element. Both insert; `add` is the `Collection` method and `offer` is the `Queue` method. For an unbounded queue like `PriorityQueue` they behave the same. - `poll()` - remove **and return** the head (the highest-priority element). Returns `null` if empty. - `peek()` - return the head **without** removing it. Returns `null` if empty. - `remove()` / `element()` - same as poll/peek but **throw** `NoSuchElementException` when empty instead of returning null. The "head" is always the minimum (or your Comparator's first element). After you `poll`, the queue reorganizes so the *new* minimum becomes the head. ## Other characteristics - **Unbounded**: it grows automatically; there is no fixed capacity limit (the constructor's `initialCapacity` is only a sizing hint). - **No nulls**: inserting `null` throws `NullPointerException` (it can't compare null). - **Not thread-safe**: concurrent modification can corrupt it; use `java.util.concurrent.PriorityBlockingQueue` for multi-threaded use. - **Comparator must be consistent**: if your Comparator returns 0 for two different elements, they are treated as equal-priority and may come out in any relative order. ## Worked example ``` PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.offer(5); pq.offer(1); pq.offer(3); pq.poll(); // 1 (smallest) pq.poll(); // 3 pq.poll(); // 5 ``` For a max-queue, pass `Comparator.reverseOrder()` so `poll` returns the largest. ## When to reach for it Greedy algorithms (Dijkstra, Prim, Huffman coding), event/task scheduling by time or priority, and "top-K largest/smallest" problems all rely on cheaply getting the current best element again and again.
- How do you make a max-priority queue?Pass a reversing comparator, e.g. new PriorityQueue<>(Comparator.reverseOrder()), or for objects Comparator.comparingInt(...).reversed().
- What's the difference between poll() and remove() on an empty queue?poll() returns null; remove() throws NoSuchElementException. Same split applies to peek() (null) vs element() (throws).
saying these in an interview costs you the question
- Saying it returns the largest by default (it returns the smallest)
- Thinking it behaves FIFO like a normal queue
- Claiming it is thread-safe
- Assuming it can store null elements