Java PriorityQueue

PriorityQueue<E> is the JDK's heap. It's a Queue, but instead of FIFO the head is always the least element according to a Comparator (or natural order if you don't supply one). offer is O(log n), poll and peek from the head are O(log n) and O(1) respectively, and the underlying storage is a flat array — no node allocation per element. That makes it the right tool for scheduler-shaped problems: "always work on whatever is most urgent next."

What "head" means here

For a FIFO queue, the head is whoever arrived first. For a PriorityQueue, the head is whoever has the smallest value at this moment — not the smallest at insertion time:

• peek() returns the current smallest.
• poll() removes the current smallest and rebalances; the next peek shows the new smallest.
• offer(x) inserts and rebalances; if x is the new smallest, the next peek returns it.

"Smallest" is decided by:

1. The Comparator you passed to the constructor, if any.
2. Otherwise, the element's natural order via Comparable. If your elements aren't Comparable and you didn't pass a Comparator, the first call that needs to compare throws ClassCastException.

There's no maximum-heap mode. If you want a max-heap, pass Comparator.reverseOrder() (or your custom comparator reversed) — that's the standard idiom and we use it in the example below.

Building one

// Natural order (Comparable elements).
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Reversed for max-heap behaviour.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Custom comparator — by length, then alphabetically.
PriorityQueue<String> byLen = new PriorityQueue<>(
    Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));

// Pre-sized + comparator (initial capacity must come first).
PriorityQueue<String> bigByLen = new PriorityQueue<>(1_000,
    Comparator.comparingInt(String::length));

// From an existing collection.
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(40, 10, 30, 20));

The single-arg constructor that takes a Collection is O(n) — it heapifies in bulk instead of n O(log n) offers. Useful when you already have all the data up front.

Iteration is NOT in priority order

This is the surprise most people hit once. Iterating a PriorityQueue walks the underlying heap array in whatever order the heap happens to store its nodes — not ascending order:

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(40, 10, 30, 20));
System.out.println(pq);                // possibly [10, 20, 30, 40]
for (int x : pq) System.out.print(x + \" \"); // possibly: 10 20 30 40
                                              // possibly: 10 40 30 20

The print order is an implementation detail of the heap layout. If you want elements in priority order, you have to drain:

while (!pq.isEmpty()) System.out.print(pq.poll() + \" \");   // sorted

Be aware of this when you forEach, stream, toArray, or just print the queue for debugging. The Stream returned by stream() is not sorted, and adding .sorted() to it requires the elements to be Comparable (or you can pass a comparator).

Mutating an element after offer breaks the heap

The priority is computed at the moment of insertion. If you put an element in and then mutate the field the comparator looks at, the heap is now in an invalid state — poll may return the wrong head, contains may miss, you lose the invariant. There is no update or decrease-key method.

The two workarounds:

• Use immutable elements — records with priority fields, or wrapper records like record Task(int priority, String name) {}. Then there's nothing to mutate after insertion.
• Remove and re-insert if you really need to change priority: pq.remove(task) is O(n) (it searches), then pq.offer(taskWithNewPriority) is O(log n).

For a small queue, remove-and-reinsert is fine. For "I am rewriting Dijkstra's algorithm and need fast decrease-key," a PriorityQueue is not the right tool — you want an indexed heap or a TreeSet of (priority, node) pairs.

null and thread safety

Same rules as the rest of Queue:

• No nulls. pq.offer(null) throws NullPointerException.
• Not thread-safe. Concurrent access needs PriorityBlockingQueue, the java.util.concurrent cousin.

A worked example: a tiny task scheduler

The program below uses a PriorityQueue to schedule tasks by priority (lower number = more urgent). It also shows the max-heap idiom and the iteration-order surprise.

Reading the run:

• toString() and forEach showed the tasks in some order — not sorted. Don't use either for debugging "is the priority right?" — drain with poll to see the real order.
• The bulk constructor produced a correctly-ordered heap in one go — that's the linear-time heapify path.
• The mutation block at the end is the foot-gun in concentrated form. We mutated the array's priority after offering it, the heap didn't get a chance to re-balance, and now peek is lying. The fix is either to use an immutable wrapper or to remove-and-offer after the change.

What's next

The next chapter covers the implementation you reach for when you want a FIFO queue or a stack or a deque — and the one the JDK Javadoc nudges you toward as the default for all three: ArrayDeque. It's the class doing most of the work behind the scenes in the previous two chapters' example code.

Practice