PriorityQueue Class in Java

Add the numbers 5, 1, 4, 2, 3 to a PriorityQueue<Integer> and print it with System.out.println(pq) — you get [1, 2, 4, 5, 3], not [1, 2, 3, 4, 5]. The queue is not broken: it only guarantees that the smallest element comes out first, and keeps everything else in a heap.

PriorityQueue (java.util.PriorityQueue) is the Java implementation of a priority queue: a class added in Java 5 that implements the Queue interface on top of a binary heap. Elements are removed not in insertion order but by priority: by default the smallest element in natural ordering (Comparable) comes out first, and a Comparator lets you define any other order. It is not a sorted queue — only the head is guaranteed to be the smallest. Duplicates are allowed, null is not, and the class is not thread-safe. Its place in the collection hierarchy is shown in Collection hierarchy in Java.

How PriorityQueue works: a binary heap (min-heap)

A PriorityQueue is implemented as a binary heap stored in an Object[] array: every element is less than or equal to its children. For the element at index i, the children are at 2*i + 1 and 2*i + 2, and the parent is at (i - 1) / 2. So the smallest element always sits in cell 0 — that is the head of the queue.

This is the heap after offer(5), offer(1), offer(4), offer(2), offer(3):

array:   [1, 2, 4, 5, 3]
index:    0  1  2  3  4

          1
        /   \
       2     4
      / \
     5   3

Every parent is smaller than its children, but there is no order between “siblings”: 4 comes before 3. A heap like this is called a min-heap. Pass a comparator with the reverse order and the largest element ends up on top — that is a max-heap (see PriorityQueue with a custom Comparator).

A new element is written to the end of the array and “sifts up”, swapping with its parent while the parent is larger. On poll() the head is removed, the last element takes its place and “sifts down”. Both operations walk at most one path from the root to a leaf, which is O(log n):

import java.util.PriorityQueue;

public class HeapDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(5);
        pq.offer(1);
        pq.offer(4);
        pq.offer(2);
        pq.offer(3);

        System.out.println(pq);        // [1, 2, 4, 5, 3]
        System.out.println(pq.poll()); // 1
        System.out.println(pq);        // [2, 3, 4, 5]
    }
}

Output:

[1, 2, 4, 5, 3]
1
[2, 3, 4, 5]

After poll() the last element, 3, moved to the root, sank below 2, and the heap is valid again. toString() prints the heap array as it is, so the printed queue tells you nothing about the order in which elements will be removed.

PriorityQueue constructors

PriorityQueue has seven constructors that differ in initial capacity, comparator and the source of initial elements. Without a comparator, the natural Comparable ordering is used. The default initial capacity is 11, and it is not a limit: the array grows automatically.

When the array is full, it is reallocated: roughly doubled while the capacity is below 64, and grown by 50% after that. Passing a capacity to the constructor makes sense when you know the number of elements in advance — it saves array copies. You cannot set a hard size limit through the constructor (the workaround is in the k largest elements).

PriorityQueue example: natural and reverse order

With natural ordering, a PriorityQueue<String> hands out strings alphabetically (strictly speaking, by Unicode character codes), and with the Collections.reverseOrder() comparator it hands them out in reverse order. Equal elements are not dropped, unlike in a Set.

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        Queue<String> queue1 = new PriorityQueue<>();
        queue1.offer("Tokyo");
        queue1.offer("Lisbon");
        queue1.offer("Oslo");
        queue1.offer("Dublin");
        queue1.offer("Dublin");
        System.out.println("Head: " + queue1.peek());
        System.out.print("Priority queue with Comparable: ");
        while (queue1.size() > 0) {
            System.out.print(queue1.remove() + " ");
        }
        System.out.println();

        PriorityQueue<String> queue2
                = new PriorityQueue<>(5, Collections.reverseOrder());
        queue2.offer("Tokyo");
        queue2.offer("Lisbon");
        queue2.offer("Oslo");
        queue2.offer("Dublin");
        queue2.offer("Dublin");
        System.out.print("Priority queue with Comparator: ");
        while (queue2.size() > 0) {
            System.out.print(queue2.remove() + " ");
        }
    }
}

Output:

Head: Dublin
Priority queue with Comparable: Dublin Dublin Lisbon Oslo Tokyo
Priority queue with Comparator: Tokyo Oslo Lisbon Dublin Dublin 

The variable queue1 is declared with the Queue interface type. offer() adds five elements and peek() shows the head without removing it. The while loop runs until the queue is empty, and on each pass remove() takes the element at the head and removes it.

For queue2 the constructor receives an initial capacity of 5 and the comparator Collections.reverseOrder(), which orders elements in the reverse of their natural ordering. The elements were added in one order and come out sorted, and “Dublin” appears twice — just as it was added. The capacity of 5 does not get in the way either: the queue would accept a sixth element.

PriorityQueue methods and time complexity

In a PriorityQueue, adding an element and removing the head take O(log n), examining the head and getting the size take O(1), and searching for or removing an arbitrary element (contains(), remove(Object)) takes O(n), because a heap is not organized for searching. The PriorityQueue Javadoc gives the same complexity.

How the offer/add, poll/remove and peek/element pairs differ in any queue is covered in Queue interface in Java. PriorityQueue has no getFirst() and getLast() methods from Java 21: the class implements neither Deque nor SequencedCollection, so pq.getFirst() does not compile.

PriorityQueue with a custom Comparator: objects and max-heap

To put your own objects into a PriorityQueue, the class must implement Comparable, or you must pass a Comparator to the constructor. A comparator also turns the queue into a max priority queue (max-heap): with Collections.reverseOrder() (or Comparator.reverseOrder()) the largest element comes out first.

import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class TaskQueue {
    record Task(String name, int priority) {}

    public static void main(String[] args) {
        PriorityQueue<Task> tasks =
                new PriorityQueue<>(Comparator.comparingInt(Task::priority));
        tasks.offer(new Task("Report", 3));
        tasks.offer(new Task("Fix a production bug", 1));
        tasks.offer(new Task("Code review", 2));

        while (!tasks.isEmpty()) {
            Task t = tasks.poll();
            System.out.println(t.priority() + " " + t.name());
        }

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.addAll(List.of(5, 1, 4, 2, 3));
        System.out.println("Max: " + maxHeap.peek());
    }
}

Output:

1 Fix a production bug
2 Code review
3 Report
Max: 5

To make tasks with the largest number come out first, use Comparator.comparingInt(Task::priority).reversed(). How to build comparators from comparing(), thenComparing() and reversed() is shown in Comparator.comparing, comparingInt, thenComparing, reversed. Avoid the popular max-heap lambda (a, b) -> b - a: subtraction overflows on numbers with large absolute values (why you should not write return a - b); the safe version is (a, b) -> Integer.compare(b, a).

What happens without Comparable and without a comparator

The compiler does not check whether elements are comparable: new PriorityQueue<Point>() compiles for any class. The error appears only at runtime:

record Point(int x, int y) {}

PriorityQueue<Point> points = new PriorityQueue<>();
points.offer(new Point(1, 2));
// JDK 11+: java.lang.ClassCastException: class Point cannot be cast to class java.lang.Comparable
// Java 8: the first offer() succeeds, the second one throws

In Java 8 the first element was written to the array without any comparison, so the error showed up on the second offer(); modern JDKs fail immediately. The fix is to implement Comparable<Point> or pass a comparator, for example Comparator.comparingInt(Point::x).

Iteration order: why the iterator does not sort

The iterator, the for-each loop, toString() and toArray() of a PriorityQueue walk the internal heap array, so the order you see does not match the priority order. Elements come out sorted only through repeated poll() calls. What does this code print?

import java.util.List;
import java.util.PriorityQueue;

public class IterationOrder {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : List.of(5, 1, 4, 2, 3)) {
            pq.offer(x);
        }

        for (int x : pq) {
            System.out.print(x + " ");
        }
        System.out.println();

        System.out.println(pq.stream().sorted().toList());

        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");
        }
        System.out.println();
        System.out.println("Size: " + pq.size());
    }
}

Output:

1 2 4 5 3
[1, 2, 3, 4, 5]
1 2 3 4 5
Size: 0

The for-each loop showed the heap array. stream().sorted() returned a sorted copy without touching the queue (toList() is Java 16+; on Java 8 use collect(Collectors.toList())). The poll() loop produced the correct order but emptied the queue. If the queue has a comparator, sort the copy with the same comparator: pq.stream().sorted(pq.comparator()). With natural ordering, comparator() returns null and sorted(null) throws NullPointerException, so there you need plain sorted().

Practical example: the k largest elements

To find the k largest elements of a large data set without sorting all of it, use a min-heap of size k: add each new element to the queue, and when the size exceeds k, remove the head — the current minimum. The queue ends up holding the k largest elements; the running time is O(n log k) and the memory is O(k).

import java.util.List;
import java.util.PriorityQueue;

public class TopK {
    static List<Integer> topK(List<Integer> numbers, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int n : numbers) {
            heap.offer(n);
            if (heap.size() > k) {
                heap.poll();          // drop the smallest
            }
        }
        return heap.stream().sorted().toList();
    }

    public static void main(String[] args) {
        List<Integer> data = List.of(5, 1, 9, 3, 7, 2, 8);
        System.out.println(topK(data, 3));
        System.out.println(topK(data, 10));
        System.out.println(topK(List.of(), 3));
    }
}

Output:

[7, 8, 9]
[1, 2, 3, 5, 7, 8, 9]
[]

If k is larger than the data set, all elements are returned; an empty list gives an empty result with no exception. The same trick gives you a “bounded priority queue” for a stream of events: only the k best values stay in memory, no matter how much data arrives. For the k smallest elements, use a max-heap — a queue with Collections.reverseOrder().

Gotchas: null, changing priority, threads

Three properties of PriorityQueue cause most bugs: the queue rejects null, it does not notice when a field of an already added object changes, and it is not protected against concurrent access from several threads. The compiler catches none of them.

null. offer(null) and add(null) throw NullPointerException: a null element cannot be compared, and poll() and peek() return null to signal an empty queue. Why null is dangerous in queues is explained in Queue and null: when poll() misleads you.

Changing priority. The heap is rearranged only on offer() and poll(). If you change the field that objects already in the queue are compared by, the removal order becomes wrong:

import java.util.Comparator;
import java.util.PriorityQueue;

public class MutablePriority {
    static class Job {
        final String name;
        int priority;
        Job(String name, int priority) { this.name = name; this.priority = priority; }
    }

    public static void main(String[] args) {
        PriorityQueue<Job> jobs = new PriorityQueue<>(Comparator.comparingInt((Job j) -> j.priority));
        Job a = new Job("A", 1);
        jobs.offer(a);
        jobs.offer(new Job("B", 2));
        jobs.offer(new Job("C", 3));

        a.priority = 10;                        // the heap does not know about this
        System.out.println(jobs.peek().name);   // A, although A now has the lowest priority

        jobs.remove(a);                         // the right way: remove,
        a.priority = 10;                        // change
        jobs.offer(a);                          // and add again
        System.out.println(jobs.peek().name);   // B
    }
}

Output:

A
B

Threads. PriorityQueue is not synchronized: concurrent offer() and poll() calls from different threads can corrupt the heap. The concurrent priority queue in Java is java.util.concurrent.PriorityBlockingQueue: it is unbounded, uses the same ordering, and its take() method waits until an element appears. Other thread-safe collections are listed in Thread-safe collections in Java. One more detail: PriorityQueue does not override equals(), so two queues with the same elements are not equal (details).

PriorityQueue vs TreeSet

PriorityQueue and TreeSet both use Comparable or Comparator, but they solve different problems. PriorityQueue is a heap: fast access to one extreme element, duplicates allowed. TreeSet is a red-black tree: fully sorted iteration, both ends, lookups in O(log n), but no duplicates.

If you need a priority queue that returns both the minimum and the maximum, PriorityQueue does not fit: use a TreeSet (if there are no duplicates) or a TreeMap with a counter for repeats. For an ordinary FIFO queue without priorities, use ArrayDeque.