Java PriorityQueue Min-Heap: Behavior and Usage

Java's PriorityQueue implements a min-heap by default: the smallest element is always at the head of the queue. This surprises some developers who expect "priority" to mean "highest priority first," but in Java the queue orders elements by their natural ordering or by 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 and removing elements 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 Heap Ordering Works

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

Ordering is determined by the elements' compareTo method (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 a second element throws a ClassCastException.

Using a Custom Comparator for Min-Heap Behavior

When elements have no natural ordering, or when you want ordering based on a specific field, pass a comparator to the constructor. This example uses a Java record to define a small data carrier:

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 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 call Collections.reverseOrder() on a Comparable type.

Performance and Memory Behavior

offer, poll, and remove() run in O(log n) time. peek and element run in O(1) time. Methods that search for an object, such as remove(Object) and contains(Object), are linear because they scan the backing array.

The backing array grows automatically when the queue exceeds its capacity. Growing allocates a larger array and copies existing elements, but it does not require reordering the heap because the heap property is preserved by array growth.

The default initial capacity is 11. If you know roughly how many 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() and collect the results.

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 compare elements 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 the element, modify it, and re-insert it.

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, Collections.min(collection) is simpler than building a queue. If you need a sorted collection with no duplicates, TreeSet is a better fit. 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.