Java PriorityQueue Tutorial with Examples

A PriorityQueue guarantees one thing: peek() returns the smallest element. It does not guarantee anything about the second smallest, and it does not iterate in order, which is why the first surprise is almost always a println that prints what looks like nonsense.

Written against Java 17.

Only the head is ordered

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.addAll(List.of(5, 1, 8, 3, 9, 2));

System.out.println(queue);        // [1, 2, 8, 5, 9, 3] — not sorted
System.out.println(queue.peek()); // 1 — always correct

The backing array is a binary heap: every node is smaller than its children, and nothing more is promised. That invariant is enough to make the minimum reachable in constant time and cheap to maintain, and it is weaker than sorted order.

toString, stream, forEach and the enhanced for loop all walk the array in storage order, so all four print the same unsorted sequence. To get priority order, drain it:

while (!queue.isEmpty()) {
    System.out.println(queue.poll());   // 1, 2, 3, 5, 8, 9
}

Draining is destructive, so copy and sort instead when the queue has to survive the read:

List<Integer> sorted = queue.stream().sorted().toList();

Complexity

Operation	Cost
offer / add	O(log n)
poll / remove()	O(log n)
peek / element	O(1)
remove(Object) / contains	O(n)

The last row is the one that catches people. Removing an arbitrary element is a linear scan to find it followed by a sift, so a scheduler that cancels tasks by calling remove(task) is quadratic in the number of cancellations. The usual fix is a tombstone — mark the entry cancelled and skip it when it reaches the head.

Comparators, and the max-heap

Natural ordering makes it a min-heap. A comparator makes it whatever you want:

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

PriorityQueue<Task> byPriority = new PriorityQueue<>(
        Comparator.comparingInt(Task::priority)
                  .thenComparing(Task::createdAt));

The tie-breaker is not decoration. A heap is not stable: two elements that compare equal come out in unspecified order, and the order can differ between runs with the same input. Adding thenComparing on a unique field makes the outcome deterministic, which is the difference between a reproducible test and an intermittent one.

Passing an initial capacity is worth it when the size is known — the default is 11 and growth copies the array:

PriorityQueue<Task> queue = new PriorityQueue<>(1000, comparator);

User-defined elements

Either implement Comparable:

record Task(String name, int priority) implements Comparable<Task> {
    @Override
    public int compareTo(Task other) {
        return Integer.compare(this.priority, other.priority);
    }
}

or supply a comparator at construction. With neither, the first offer of a second element throws ClassCastException — not at construction, and not on the first element, because nothing has needed to compare yet.

Use Integer.compare(a, b) rather than a - b. Subtraction overflows: with a = Integer.MAX_VALUE and b = -1 the difference wraps to a negative number and the ordering inverts. It is a rare input and a genuinely confusing bug.

The comparator must agree with equals

record Task(String name, int priority) { }

PriorityQueue<Task> queue = new PriorityQueue<>(Comparator.comparingInt(Task::priority));
queue.offer(new Task("a", 1));

queue.remove(new Task("b", 1));   // removes "a" — same priority, so "equal" to the heap

remove(Object) and contains use the comparator when one is present, not equals. A comparator that only looks at priority makes every task with that priority interchangeable, so the wrong one is removed and no exception is raised.

Comparing on all identifying fields — priority first, then something unique — fixes the removal and the stability problem at once.

No nulls, and the memory that is not bounded

queue.offer(null);   // NullPointerException

null cannot be ordered, so it is rejected. That is also what makes poll() returning null unambiguously mean “empty”, which is the drain idiom:

Task task;
while ((task = queue.poll()) != null) {
    process(task);
}

More importantly, PriorityQueue is unbounded. The constructor’s capacity argument is an initial size, not a limit, and offer always returns true. A producer faster than its consumer grows the array until the heap is exhausted — the queue converts backpressure into an OutOfMemoryError.

For a work queue crossing threads, use PriorityBlockingQueue, and note that it is unbounded too. A genuinely bounded priority queue needs a semaphore around it or a check before every offer.

It is not thread-safe

PriorityQueue has no synchronisation. Two threads offering concurrently can corrupt the heap invariant, after which poll returns elements in the wrong order — silently, with no exception.

PriorityBlockingQueue is the concurrent version, and it is what an ExecutorService needs if tasks are to run in priority order rather than arrival order. Note that a ThreadPoolExecutor given one will only honour priorities among tasks that are already queued — while the pool is below its core size, every submission starts a thread immediately and nothing queues at all.

How the heap actually works

The array holds the tree implicitly: the children of index i live at 2i + 1 and 2i + 2, and the parent of i is at (i - 1) / 2. There are no node objects and no pointers, which is why a heap has better locality than a balanced tree despite being a tree.

offer appends at the end and sifts up — swap with the parent while the parent is larger. The new element travels at most the height of the tree, which is log n.

poll takes index 0, moves the last element into its place, and sifts down — swap with the smaller child while a child is smaller. Again at most log n swaps.

Two consequences follow from that and explain most of the behaviour above. Building a heap from a collection is O(n), not O(n log n), because heapify works bottom-up and most nodes barely move — which is why new PriorityQueue<>(collection) beats offering elements one at a time. And nothing in either operation touches the elements that are not on the path from the leaf to the root, so the rest of the array keeps whatever arrangement it had. That is the mechanical reason iteration order looks arbitrary: it is a real ordering, just not a total one.

Where it earns its place

The natural fit is “process the most urgent thing next” without keeping the whole set sorted. Two concrete shapes:

Top-k with a bounded heap. To keep the largest k elements of a large stream, use a min-heap of size k and evict the head:

PriorityQueue<Integer> topK = new PriorityQueue<>(k);
for (int value : stream) {
    topK.offer(value);
    if (topK.size() > k) {
        topK.poll();          // discard the smallest
    }
}

That is O(n log k) time and O(k) memory, against O(n log n) and O(n) for sorting everything. The counter-intuitive part is that finding the largest k uses a min-heap, because the element you need to discard cheaply is the smallest of the ones you are keeping.

Graph search. Dijkstra’s algorithm and A* both need “the closest unvisited node”, which is exactly poll(). Because remove(Object) is linear, the standard implementation does not update priorities in place — it offers a new entry and skips stale ones on the way out.

Compare with Queue and Deque for FIFO ordering. More in the Java guides.

Frequently asked questions

Why does printing a PriorityQueue show unsorted elements?

It is a binary heap, and only the head is guaranteed to be the minimum. toString walks the backing array in storage order. Drain with poll to get priority order.

How do I make a max-heap?

Pass Comparator.reverseOrder(), or a comparator that inverts your own ordering, to the constructor.

Is a PriorityQueue stable?

No. Elements that compare equal come out in unspecified order. Add a tie-breaker on a unique field with thenComparing if the order must be reproducible.

Why does remove() delete the wrong element?

remove(Object) uses the comparator, not equals. If the comparator only looks at one field, every element with that value is interchangeable.

What is the cost of remove(Object)?

O(n) — a linear scan to find the element, then a sift. For frequent cancellations, mark entries as cancelled and skip them at the head instead.

Why do I get a ClassCastException on the second insert?

The element type implements neither Comparable nor was a comparator supplied. Nothing needed comparing until a second element arrived.

Can a PriorityQueue hold null?

No. null cannot be ordered, and its rejection is what makes poll() returning null mean “empty” unambiguously.

Is PriorityQueue bounded?

No. The capacity argument is an initial size. A producer outrunning its consumer grows it until the heap is exhausted; bound it yourself if that is possible.

Is it thread-safe?

No. Use PriorityBlockingQueue for concurrent access — unsynchronised concurrent writes corrupt the heap and produce wrong ordering with no exception.

How do I keep the top k elements of a large stream?

A min-heap of size k: offer everything, and poll whenever the size exceeds k. O(n log k) time and O(k) memory.