skip to content

PriorityQueue

A binary heap that dequeues by priority in O(log n), using natural ordering or a Comparator. The catch interviewers test is that iteration and toString are not sorted; repeated poll gives ordered output, and it drains the queue.

part ofJavaread it →
on this pageshow

questions

6

What is a PriorityQueue in Java and how do you get elements out in priority order?

level: juniorimportance: must knowfreq 70%

answer

  1. Min-heap by default: smallest out first
  2. Natural order OR a Comparator
  3. poll removes head, peek looks
  4. poll/peek return null; remove/element throw
  5. No nulls, not thread-safe, unbounded

basics

~20 s

A 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 s

PriorityQueue 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

for a junior

Knows it returns the smallest first by default, uses offer/poll/peek, and that it isn't FIFO.

for a middle

Distinguishes natural order vs Comparator, builds a max-queue, knows the null/throws vs null-return behavior and no-null rule.

for a senior

Explains the heap backing, thread-safety (PriorityBlockingQueue), comparator consistency, and chooses it for greedy/top-K problems.

for a principal

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 - **Cost**: the Javadoc's implementation note gives O(log n) time for `offer`, `add`, `poll` and `remove()`, constant time for `peek`, `element` and `size`, and linear time for `remove(Object)` and `contains(Object)`. - **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`, even with a comparator that could order it, such as `Comparator.nullsFirst(...)`. `poll` and `peek` use `null` to signal an empty queue, so a stored null would be ambiguous. - **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 ``` Repeated `poll` or `remove()` gives this order by draining the queue. The iterator, which a for-each loop and `toString` use, is "not guaranteed to traverse the elements of the priority queue in any particular order": printed right after the three offers, this queue shows `[1, 5, 3]` on JDK 27. For ordered traversal, the Javadoc suggests `Arrays.sort(pq.toArray())`. 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 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

java.util.PriorityQueue
Java 1.5

context

open as a page

Why is iterating over a PriorityQueue not the same as getting elements in sorted order?

level: middleimportance: must knowfreq 62%

basics

~20 s

Iterating (for-each, iterator, toArray, toString) walks the internal heap array, which is only partially ordered - just the head is guaranteed smallest. Repeatedly calling poll() drains them in priority order; sorting a copy leaves the queue intact.

open as a page

How do you control PriorityQueue ordering (e.g. build a max-heap or order by an object field), and what must the Comparator guarantee?

level: middleimportance: should knowfreq 58%

basics

~10 s

Pass a Comparator to the constructor: PriorityQueue<>(Comparator.reverseOrder()) for a max-heap, or Comparator.comparingInt(Task::getPriority) to order by a field. Without one it uses the element's natural ordering, so the type must be Comparable.

open as a page

How does Java's PriorityQueue work inside: its heap array, sifting on offer and poll, array growth, and bulk-constructor heapify?

level: middleimportance: should knowfreq 46%

basics

~20 s

PriorityQueue keeps a binary min-heap in an Object array: offer sifts the new element up from the end, poll sifts the last element down from the root. The array grows by copying, and building from an unordered collection runs O(n) heapify.

open as a page

What are the time complexities of PriorityQueue's offer, poll, peek, and contains/remove(Object) operations, and why?

level: seniorimportance: should knowfreq 55%

basics

~20 s

offer and poll are O(log n) because they bubble an element up or down the heap. peek is O(1) - the head is at index 0. contains(o) and remove(o) are O(n) because they have to scan the array linearly.

open as a page

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

level: seniorimportance: should knowfreq 40%

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.

open as a page