Java PriorityQueue Min Heap: Behavior and Usage

java priorityqueue min heap requires a clear understanding of the core syntax, runtime behavior, and practical implementation patterns demonstrated in the examples below.

Java's PriorityQueue implements a min-heap by default, which means the smallest element is always at the head of the queue. This behavior surprises many developers who expect "priority" to mean "highest priority first" — but in Java, the queue orders elements according to their natural ordering or a provided comparator, and poll() returns the least element.

Creating a Min-Heap with PriorityQueue

The simplest way to create a min-heap is to instantiate PriorityQueue with no arguments:

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

This uses the natural ordering of Integer, so poll() returns the smallest value currently in the queue. Adding elements and removing them follows heap semantics:

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(30);
minHeap.offer(10);
minHeap.offer(20);

System.out.println(minHeap.peek());  // 10
System.out.println(minHeap.poll());  // 10
System.out.println(minHeap.poll());  // 20

offer() inserts an element in O(log n) time, and poll() removes the head in O(log n) time. peek() returns the head without removing it in O(1) time. These are the operations you will use most often when treating PriorityQueue as a min-heap.

How the Heap Ordering Works

The PriorityQueue is backed by a binary heap stored in an array. The heap property is maintained after every insertion and removal: each parent node is less than or equal to its children (for a min-heap). This guarantees that the minimum element is always at index 0 of the backing array.

The ordering itself is determined by the compareTo method of the elements (natural ordering) or by a Comparator supplied at construction time. If you store custom objects, they must implement Comparable, or you must pass a comparator; otherwise, inserting the second element throws a ClassCastException.

Using a Custom Comparator for Min-Heap Behavior

When your elements do not have a natural ordering, or when you want ordering based on a specific field, pass a comparator to the constructor:

record Task(int priority, String name) {}

PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority)
);

taskQueue.offer(new Task(3, "low"));
taskQueue.offer(new Task(1, "high"));
taskQueue.offer(new Task(2, "medium"));

System.out.println(taskQueue.poll().name());  // "high"

The comparator defines what "minimum" means. In this example, the task with the lowest priority number is considered the minimum and is polled first. If you want the highest priority number to be polled first, reverse the comparator:

PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed()
);

Converting to a Max-Heap

A common requirement is a max-heap, where the largest element is polled first. Since PriorityQueue is a min-heap by default, you achieve max-heap behavior by reversing the comparator:

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

For custom objects, use Comparator.comparingInt(...).reversed() or Comparator.reverseOrder() on a comparable type. Note that Collections.reverseOrder() also works for types that implement Comparable.

Performance Characteristics and Memory Behavior

All heap operations — offer, poll, and remove — run in O(log n) time. peek and element run in O(1) time. The backing array grows automatically when the queue exceeds its capacity, which involves copying the array and re-establishing the heap property.

The initial capacity defaults to 11. If you know the approximate number of elements you will store, construct the queue with a larger initial capacity to avoid repeated resizing:

PriorityQueue<Integer> minHeap = new PriorityQueue<>(1000);

PriorityQueue is not thread-safe. Concurrent access requires external synchronization, or you should use PriorityBlockingQueue when multiple threads read and write the queue. The iterator returned by iterator() does not guarantee any particular order — it walks the backing array, not the heap order. If you need to iterate elements in sorted order, repeatedly call poll() into a list instead.

Common Pitfalls with PriorityQueue as a Min-Heap

Three issues trip up developers regularly.

Null elements are not allowed. Inserting null throws NullPointerException because the queue must call compareTo or the comparator during offer().

The iterator order is not sorted. A common mistake is iterating the queue and expecting ascending order. The backing array only guarantees the heap property, not full sorting. To get sorted output, drain the queue:

List<Integer> sorted = new ArrayList<>();
while (!minHeap.isEmpty()) {
    sorted.add(minHeap.poll());
}

Modifying elements after insertion breaks the heap property. If you change a field that participates in the comparator after the element is already in the queue, the queue will not re-heapify automatically. The element stays at its original position, and subsequent poll() calls may return elements out of order. Remove and re-insert the element after modification.

Choosing Between PriorityQueue and Other Structures

PriorityQueue is the right choice when you need repeated access to the smallest (or largest) element with logarithmic insertion and removal. Common use cases include scheduling tasks by priority, merging sorted streams, computing the k smallest or largest elements, and graph algorithms such as Dijkstra's.

If you only need the single smallest element once, sorting the collection and taking the first element is simpler. If you need a fully sorted collection that supports efficient insertion and removal at both ends, consider TreeSet (no duplicates) or a sorted list. If you need thread-safe priority semantics, PriorityBlockingQueue provides the same ordering guarantees with blocking behavior.

The min-heap behavior of PriorityQueue is a deliberate design choice: it gives you the smallest element in O(1) lookup and O(log n) insertion and removal, which is the right tradeoff for most priority-based algorithms. Understanding that the queue is a heap, not a sorted list, is the key to using it correctly.