Senior 3 min · March 06, 2026

Java PriorityQueue — Mutating Fields Breaks Heap Order

Q: Why does iterating over a PriorityQueue not give sorted output?

A heap is not a sorted array — it only guarantees that the root is the minimum. The rest of the array satisfies the heap property but is not in sorted order. To get sorted output, repeatedly call poll() until the queue is empty, or copy to a list and sort.

Q: What is the difference between PriorityQueue and TreeSet?

PriorityQueue allows duplicates and is faster for insert/delete (O(log n) with a smaller constant). TreeSet does not allow duplicates, supports range queries (first(), last(), headSet()), and iterates in sorted order. For a priority queue use case (dynamic priority processing with duplicate priorities), PriorityQueue is almost always better.

Q: Is PriorityQueue thread-safe?

No. PriorityQueue is not thread-safe. For concurrent access from multiple threads, use PriorityBlockingQueue which provides thread-safe operations with blocking on empty queues.

PriorityQueue does not re-heapify after object field changes; low-priority tasks run before high-priority.

Naren · Founder

Plain-English first. Then code. Then the interview question.

About

● Production Incident 🔎 Debug Guide

⚡Quick Answer

Java's PriorityQueue is a min-heap by default — poll() returns the smallest element.
Pass a Comparator to change ordering; use Comparator.reverseOrder() for a max-heap.
Iteration does not produce sorted order — only poll() and peek() respect the heap ordering.
offer() and poll() are O(log n); peek() is O(1); contains() is O(n).
Production trap: iterating the queue assuming sorted order will give incorrect results. Always poll() repeatedly.
Not thread-safe — use PriorityBlockingQueue for concurrent access.

Plain-English First

A PriorityQueue is like a line where the most important person (lowest number) goes first, no matter when they joined. You can change what 'important' means by providing a Comparator.

Basic Min-Heap Usage

The code demonstrates two common patterns: the default min-heap and the max-heap using Comparator.reverseOrder(). In the min-heap, poll() returns the smallest element each time. The max-heap reverses the natural ordering so the largest element comes out first. The internal representation is a binary heap array, which means the elements are not fully sorted — only the root is guaranteed to be the smallest (or largest for max-heap).

ExampleJAVA

package io.thecodeforge.java.collections;

import java.util.PriorityQueue;

public class PriorityQueueBasics {
    public static void main(String[] args) {
        // Min-heap by default
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(5);
        minHeap.add(1);
        minHeap.add(9);
        minHeap.add(3);
        minHeap.add(7);

        System.out.println("peek: " + minHeap.peek());  // 1 — smallest, no removal

        // poll() removes and returns the smallest
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " ");
        }
        // 1 3 5 7 9 — ascending order

        System.out.println();

        // Max-heap using Comparator.reverseOrder()
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.addAll(java.util.List.of(5, 1, 9, 3, 7));

        while (!maxHeap.isEmpty()) {
            System.out.print(maxHeap.poll() + " ");
        }
        // 9 7 5 3 1 — descending order
    }
}

Output

peek: 1

1 3 5 7 9

9 7 5 3 1

Production Insight

Many engineers mistakenly assume max-heap by default, causing priority inversion in production.

PriorityQueue resizes its internal array when capacity is exceeded, costing O(n) per resize.

Rule: always verify ordering with a test on your comparator before relying on it in critical queue processing.

Key Takeaway

PriorityQueue is min-heap by default.

Use Comparator.reverseOrder() for max-heap.

Always test ordering with sample data before production use.

Custom Objects with Comparator

When your objects don't have a natural ordering, you provide a Comparator. The example uses a Task record with priority and deadline fields. The comparator sorts by priority ascending, then by deadline ascending. This is typical for job schedulers where you want to process urgent tasks (lower priority number) first, and tie-break by deadline. Note that if the comparator is inconsistent with equals (i.e., compare returns 0 when equals returns false), the queue may misbehave during remove(Object) or contains() operations.

ExampleJAVA

package io.thecodeforge.java.collections;

import java.util.PriorityQueue;

public class TaskScheduler {

    record Task(String name, int priority, long deadline) {}

    public static void main(String[] args) {
        // Order by priority ascending (1 = most urgent)
        PriorityQueue<Task> queue = new PriorityQueue<>(
            Comparator.comparingInt(Task::priority)
                      .thenComparingLong(Task::deadline)
        );

        queue.add(new Task("Deploy fix",       1, 1700000000L));
        queue.add(new Task("Write tests",      3, 1700001000L));
        queue.add(new Task("Code review",      2, 1700000500L));
        queue.add(new Task("Fix critical bug", 1, 1699999000L));

        while (!queue.isEmpty()) {
            Task t = queue.poll();
            System.out.printf("[%d] %s%n", t.priority(), t.name());
        }
    }
}

Output

[1] Fix critical bug

[1] Deploy fix

[2] Code review

[3] Write tests

Production Insight

If you mutate the priority field of a Task after it's inserted, the heap structure is not automatically updated.

The queue will contain stale ordering, leading to incorrect poll() results — critical tasks may be skipped.

Rule: treat objects in a PriorityQueue as immutable with respect to the comparator fields after insertion.

Key Takeaway

Define a Comparator that exactly reflects your priority rules.

Do not mutate priority fields while the object is in the queue.

Ensure comparator consistency with equals for correct remove/contains behavior.

Dijkstra's Shortest Path — Classic PriorityQueue Use

Dijkstra's algorithm is the textbook use case for PriorityQueue. We maintain a min-heap of [distance, node] pairs. At each step, we poll the node with the current shortest distance. If we find a shorter path to a neighbor, we update the distance and push the updated pair onto the heap. The stale entry check (if d > dist[u]) is crucial: old entries with larger distances are ignored, preventing the algorithm from processing obsolete states.

ExampleJAVA

package io.thecodeforge.java.collections;

import java.util.*;

public class Dijkstra {
    // Finds shortest distances from source to all nodes
    static int[] shortestPaths(int[][] graph, int src) {
        int n = graph.length;
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        // Min-heap: [distance, node]
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, src});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], u = curr[1];

            if (d > dist[u]) continue;  // stale entry

            for (int v = 0; v < n; v++) {
                if (graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
        return dist;
    }
}

Output

// Core of Dijkstra — PriorityQueue makes it O((V+E) log V)

Production Insight

Without the stale entry check (d > dist[u]), Dijkstra might process outdated distances, leading to incorrect results.

In production systems, always include stale entry filtering when using a mutable priority in Dijkstra-like algorithms.

The same pattern applies to A* search and any best-first search where distances are updated.

Key Takeaway

Dijkstra's algorithm needs a min-heap for efficiency.

Stale entry filtering is essential for correctness.

PriorityQueue works because we only care about the smallest distance at each step.

PriorityQueue Internal Structure and Performance

Java's PriorityQueue is backed by a dynamic array (Object[] queue) that stores elements in a binary heap structure. The heap property ensures that the parent is less than or equal to its children (for the default comparator). This structure allows O(log n) insertion (offer) and O(log n) removal of the root (poll). However, contains() and remove(Object) require a linear scan of the array (O(n)) because the heap is not sorted. The initial capacity is 11, and it grows by 50% when full, which involves copying the array.

Production Insight

Contains() is O(n) — do not call it in a hot path. If you need fast membership checks, maintain a separate HashSet.

For large priority queues (millions of elements), the array growth can cause memory spikes. Pre-size with initialCapacity if you know the expected size.

The default initial capacity of 11 is fine for typical use, but consider tuning if you add many elements.

Key Takeaway

Prefer poll() over contains() for performance.

Pre-size the PriorityQueue when average size is known.

Internal array grows dynamically — expect occasional O(n) resizing.

PriorityQueue vs TreeSet vs Arrays.sort() — When to Use Which

Each tool has a different contract

PriorityQueue: dynamic, allows duplicates, O(log n) insert/delete of the smallest element, no in-order iteration.
TreeSet: sorted set, no duplicates, O(log n) insert/delete, supports in-order iteration and range queries.
Arrays.sort(): one-shot sorting of a fixed collection, O(n log n), no dynamic operations.

Use PriorityQueue when you need a dynamic priority-processing pipeline with possible duplicates (e.g., job scheduler). Use TreeSet when you need an sorted set without duplicates and you need to iterate in order or query subsets. Use Arrays.sort() when you have a fixed list that you need sorted once.

Production Insight

Using TreeSet to process tasks in priority order is wrong if duplicate priorities are allowed — TreeSet will silently drop duplicates.

Arrays.sort() is fine for immutable lists but not for a dynamic queue where elements arrive over time.

Choosing the wrong collection can lead to data loss or incorrect processing order.

Key Takeaway

Use PriorityQueue for dynamic, duplicate-allowing priority processing.

Use TreeSet if you need a sorted set with no duplicates and range queries.

Use Arrays.sort() for one-time sorting of a static collection.

● Production incidentPOST-MORTEMseverity: high

Mutating Priority Fields in a PriorityQueue Breaks Ordering

Symptom

Tasks are not executed in expected priority order; some low-priority tasks executed before high-priority ones.

Assumption

The priority field of the task object can be updated without affecting the queue order.

Root cause

PriorityQueue does not re-heapify after objects' comparator-relevant fields are changed. The heap is only maintained at insertion and removal times.

Fix

Remove the object from the queue, update its fields, then re-insert it. Alternatively, mark objects as immutable with respect to the comparator after insertion.

Key lesson

Never mutate objects while they are in a PriorityQueue.
If updates are needed, remove and re-add the object.
Consider using a separate data structure for mutable priority tasks.
Always test your queue logic with mutation scenarios.

Production debug guideSymptom → Action Guide for Common PriorityQueue Problems4 entries

Symptom · 01

poll() returns wrong element (out of order)

→

Fix

Check if any object's fields used in Comparator were modified after insertion. Heap only repairs on insert/remove.

Symptom · 02

ClassCastException when adding custom object without Comparator

→

Fix

Ensure the class implements Comparable or pass a Comparator to the constructor.

Symptom · 03

Iteration order is not sorted

→

Fix

This is expected. Do not rely on iterator order. Use poll() in a loop to get sorted order.

Symptom · 04

NullPointerException on add or poll

→

Fix

PriorityQueue does not allow null elements. Check for null before adding and ensure no nulls are stored.

★ Quick Debug Cheat Sheet for PriorityQueueCommon symptoms and immediate actions when PriorityQueue misbehaves

poll() returns wrong element−

Immediate action

Check for mutated objects in queue

Commands

print each element's priority fields before poll

verify comparator logic in isolation on a sorted list

Fix now

Remove and re-add all elements after updating comparator fields.

ClassCastException+

Iterator shows unsorted order+

PriorityQueue vs TreeSet vs LinkedList (as Queue)

Feature	PriorityQueue	TreeSet	LinkedList
Duplicates allowed	Yes	No	Yes
Ordering guarantee	Min-heap on `poll()`	Sorted iteration	Insertion order
Null allowed	No	No	Yes
Random access	No	No (iter only)	Yes
Thread-safe	No	No	No

Key takeaways

Java PriorityQueue is a min-heap

poll() returns the smallest element.

Use Comparator.reverseOrder() for a max-heap; use Comparator.comparing() for custom objects.

Iteration order is NOT sorted

only poll() respects the heap ordering.

poll() removes and returns the head; peek() returns without removing; offer()/add() inserts.

PriorityQueue does not allow null elements

it will throw NullPointerException.

Mutating comparator-relevant fields of an object while it is in the queue causes incorrect ordering.

Common mistakes to avoid

4 patterns

Mutating priority fields while object is in queue

Symptom

poll() returns elements in wrong order; some elements may seem lost. The queue no longer respects the intended priority.

Fix

Remove the object before mutation, then re-insert it. Alternatively, use an immutable wrapper and replace the object entirely.

Assuming iteration order is sorted

Symptom

When you print the queue via for-each, you don't see elements in sorted order. This can cause confusion during debugging.

Fix

Use poll() in a loop to extract elements in sorted order, or copy to a list and sort with Collections.sort().

Using PriorityQueue without a Comparator for a custom class that does not implement Comparable

Symptom

ClassCastException at runtime when adding elements.

Fix

Implement Comparable on your class or pass a Comparator to the PriorityQueue constructor.

Not pre-sizing the queue when many elements are added

Symptom

Multiple array resizes cause performance degradation and memory spikes, leading to GC pauses.

Fix

Use PriorityQueue(initialCapacity) constructor if you know the expected number of elements.

INTERVIEW PREP · PRACTICE MODE

Interview Questions on This Topic

Q01JUNIOR

How do you create a max-heap using Java's PriorityQueue?

Q02JUNIOR

What is the time complexity of PriorityQueue.poll()?

Q03SENIOR

Why does iterating a PriorityQueue not yield elements in sorted order?

Q04SENIOR

What happens if you modify the priority of an object already in a Priori...

Q01 of 04JUNIOR

How do you create a max-heap using Java's PriorityQueue?

ANSWER

Use Comparator.reverseOrder() as the constructor argument: new PriorityQueue<>(Comparator.reverseOrder()). This reverses the natural ordering, so the largest element is at the root.

FAQ · 3 QUESTIONS

Frequently Asked Questions

Why does iterating over a PriorityQueue not give sorted output?

What is the difference between PriorityQueue and TreeSet?

Is PriorityQueue thread-safe?

🔥

That's Collections. Mark it forged?

3 min read · try the examples if you haven't