PriorityQueue in Java

PriorityQueue in Java is a min-heap by default, the element with the lowest value is always at the head of the queue. Unlike a regular queue that processes elements in insertion order, PriorityQueue processes them by priority. It is backed internally by a binary heap, which gives it O(log n) insert and remove operations. To use it as a max-heap or sort by a custom field, you need a Comparator.

This article covers every constructor, all key methods with time complexity, how to set up min and max heaps, custom Comparator patterns, the iteration gotcha that trips up candidates in interviews, and the most common interview problem patterns where PriorityQueue is the right tool.

Key Takeaways

What Is PriorityQueue in Java?

What is PriorityQueue in Java?

PriorityQueue in Java is a queue where elements are retrieved in priority order rather than insertion order. It is backed by a binary min-heap internally, meaning the element with the smallest value according to natural ordering is always at the head. Every insertion and removal restructures the heap to maintain this property. PriorityQueue is part of java.util and implements the Queue interface. It allows duplicate elements but does not permit null values.

What is the class hierarchy of PriorityQueue in Java?

PriorityQueue extends AbstractQueue, which implements Queue, which extends Collection, which extends Iterable. The full hierarchy is: Iterable → Collection → Queue → AbstractQueue → PriorityQueue.

PriorityQueue Constructors in Java

What are the constructors of PriorityQueue in Java?

Java provides four main constructors for PriorityQueue. The Comparator constructor is the most important one for interview use, as it is how you switch between min-heap and max-heap behavior.

Example: Creating PriorityQueues with different constructors

// Default min-heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Min-heap with initial capacity
PriorityQueue<Integer> pq = new PriorityQueue<>(20);
// Max-heap using Collections.reverseOrder()
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// Max-heap with initial capacity
PriorityQueue<Integer> maxHeap2 = new PriorityQueue<>(20, Collections.reverseOrder());

PriorityQueue Methods in Java

What are the key methods of PriorityQueue in Java?

Java PriorityQueue provides the following key methods. All structural modifications, adding and removing elements trigger heap restructuring, which is why insert and poll operations are O(log n).

What is the difference between add() and offer() in PriorityQueue?

For the default unbounded PriorityQueue, add() and offer() behave identically, both insert the element and return true. The distinction applies only to bounded queues: add() throws an IllegalStateException when the queue has reached capacity, while offer() returns false instead. Since Java’s standard PriorityQueue is unbounded (it grows dynamically), this distinction rarely matters in practice but is a frequent interview question.

What is the difference between poll() and peek() in PriorityQueue?

poll() removes the head element from the queue and returns it. If the queue is empty, it returns null. peek() returns the head element without removing it, also returning null if empty. Use peek() when you need to inspect the top element without modifying the queue, for example, when comparing the top of two heaps without advancing either.

Min Heap and Max Heap Using PriorityQueue in Java

Is Java PriorityQueue a min-heap or max-heap by default?

Java PriorityQueue is a min-heap by default. The element with the smallest value according to natural ordering is always at the head. When you call poll(), it removes and returns the smallest element first. For integers, this means 1 comes out before 5 before 10. For strings, natural ordering is lexicographic. This default behavior is the source of the most common PriorityQueue interview mistake, using a default PriorityQueue when a max-heap is needed, or vice versa.

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

Pass Collections.reverseOrder() as the Comparator when constructing the PriorityQueue. This reverses the natural ordering so the largest element sits at the head instead of the smallest.

Max-heap using Collections.reverseOrder()

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.add(3);
maxHeap.add(10);
maxHeap.add(7);
System.out.println(maxHeap.poll()); // Output: 10
System.out.println(maxHeap.poll()); // Output: 7
System.out.println(maxHeap.poll()); // Output: 3

How do you create a PriorityQueue with a custom Comparator in Java?

For non-primitive types or when sorting by a specific field, pass a lambda or Comparator implementation to the PriorityQueue constructor. This is the most interview-relevant usage; interval scheduling, task scheduling, and object sorting problems all require custom Comparators.

Custom Comparator – sort int[] arrays by second element (common in interval problems)

// Sort int[] arrays by second element (end time in interval problems)
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

// Sort by object field — example: Person sorted by age ascending
PriorityQueue<Person> byAge = new PriorityQueue<>((a, b) -> a.age - b.age);

// Sort by object field descending
PriorityQueue<Person> byAgeDesc = new PriorityQueue<>((a, b) -> b.age - a.age);

Common PriorityQueue Comparator patterns used in interview problems:

PriorityQueue Time and Space Complexity

What is the time complexity of PriorityQueue operations in Java?

Every structural operation, adding and removing elements, triggers heap restructuring (sifting up or sifting down), which is why those operations are O(log n). contains() and remove(Object) require a linear scan of the internal backing array, making them O(n). This is why using PriorityQueue for membership checks is inefficient, use a HashSet alongside if you need fast lookups.

Iterating a PriorityQueue in Java

Does iterating a PriorityQueue in Java return elements in priority order?

No. Iterating a PriorityQueue with a for-each loop or iterator does NOT return elements in priority order. It returns elements in the internal heap array order, which is undefined from the caller’s perspective. This surprises most candidates the first time they see it, and it is a common interview gotcha. To process elements in priority order, use poll() in a loop.

CORRECT – Process in priority order using poll()

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5); pq.add(1); pq.add(3);

// CORRECT: poll() processes in ascending order
while (!pq.isEmpty()) {
    System.out.println(pq.poll()); // prints: 1, 3, 5
}

WRONG – for-each loop does NOT return elements in priority order

// WRONG: for-each does NOT guarantee priority order
for (int x : pq) {
    System.out.println(x); // undefined order — do NOT use this
}

PriorityQueue Interview Patterns

In which interview problems is PriorityQueue commonly used?

PriorityQueue is the go-to data structure for a specific family of interview problems. Understanding which pattern maps to which heap type is the skill that separates candidates who solve these correctly from those who get the approach right but the implementation wrong. See also: heap data structure guide.

Interview Pattern Rule: Kth Largest problems always use a min-heap of size K, not a max-heap. The logic: keep only the K largest elements seen so far. If a new element beats the current minimum (heap head), swap it in. After processing all elements, the heap head is the Kth largest. Getting the heap type wrong here, reaching for a max-heap instead, is one of the most common interview mistakes on heap problems.

Conclusion

Java’s PriorityQueue gives you a min-heap by default with O(log n) insert and poll. The real interview skill is not knowing the API; it is knowing when to use a min-heap versus a max-heap and recognizing which pattern a problem belongs to before you write a single line of code. Most heap problems at FAANG companies involve one of five patterns: Kth element, merge K sorted, top K frequent, shortest path, or interval scheduling. Getting fluent with those patterns and the corresponding heap setup is what converts PriorityQueue knowledge into correct interview solutions.

FAQs: PriorityQueue in Java

Q1. Can PriorityQueue store null values in Java?

No. PriorityQueue does not permit null elements. Inserting null throws a NullPointerException immediately. This is different from some other Java collections like LinkedList or ArrayDeque that allow null. If you need a priority queue that can hold null, you need a custom implementation.

Q2. Is PriorityQueue thread-safe in Java?

No. PriorityQueue is not thread-safe. If multiple threads access the same PriorityQueue concurrently and at least one modifies it, external synchronization is required. For concurrent use cases, use PriorityBlockingQueue from java.util.concurrent, which provides the same priority ordering with built-in thread safety.

Q3. What is the default initial capacity of PriorityQueue in Java?

The default initial capacity of PriorityQueue in Java is 11. The queue grows automatically as elements are added, capacity roughly doubles when the backing array runs out of space. You rarely need to set this manually unless you are optimizing for a very large known dataset size.

Q4. What is the difference between PriorityQueue and TreeSet in Java?

PriorityQueue allows duplicate elements and provides O(log n) access only to the minimum element (or maximum with a custom Comparator). TreeSet does not allow duplicates and provides O(log n) access to any element including min, max, floor, and ceiling. Use PriorityQueue when you need repeated access to the minimum or maximum element and duplicates are expected. Use TreeSet when you need a sorted set with range operations and duplicates are not allowed.

Recommended Reads:

• System.out.println in Java: How It Works, Syntax, and Examples
• Advanced Java Interview Questions and Answers for Coding Interview
• How to Iterate a Map in Java
• How to Remove All Non-alphanumeric Characters From a String in Java?
• Top Java Interview Questions for Software Developers in 2026: What do Interviewers Test?