PriorityQueue

#Introduction

PriorityQueue is one of the most important Queue implementations for interviews because it introduces a completely different concept:

The head is determined by priority, not insertion order.

Internally, PriorityQueue uses a binary heap, specifically a min-heap by default.

#What is PriorityQueue?

Package:

java.util.PriorityQueue

Declaration:

public class PriorityQueue<E>
        extends AbstractQueue<E>
        implements Serializable

Key characteristics:

• Allows duplicate elements
• Does not allow null
• Not thread-safe
• Default ordering is natural ordering
• Custom ordering can be supplied using a Comparator
• The head contains the highest-priority element
• Default priority = smallest element
• Internally uses a binary heap

#PriorityQueue Is Not FIFO

This is the first thing to remember. A normal Queue with 10 → 20 → 30 returns 10 from poll() because it was inserted first. A PriorityQueue:

Queue<Integer> queue = new PriorityQueue<>();

queue.offer(30);
queue.offer(10);
queue.offer(20);

The head is 10 because 10 has the highest priority under natural ordering. So insertion order ≠ processing order.

Default Priority

For numbers, the smallest number has the highest priority.

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

pq.offer(50);
pq.offer(10);
pq.offer(30);
pq.offer(20);

Repeated poll():

10
20
30
50

This behaves like a min-priority queue.

#Internal Structure — Binary Heap

PriorityQueue is backed by an array representing a complete binary tree.

Array Representation

The tree above is represented in an array as:

This is why PriorityQueue doesn't need separate Node objects like LinkedList.

Why a Complete Binary Tree?

A heap must be a complete binary tree:

• Every level is completely filled except possibly the last.
• The last level is filled from left to right.

This makes the tree compact and efficiently representable using an array.

Parent/Child Index Formula

For an element at index i:

Example: index 0 → left = 1, right = 2. Index 1 → parent = 0, left = 3, right = 4. These formulas are frequently asked in coding interviews.

#offer() and Sift-Up

pq.offer(5);

Sift-Up Example

Heap is 10 → (20, 30). Insert 5:

Complexity of offer()

The new element may move from the bottom to the root. Heap height is O(log n), therefore offer() → O(log n).

#peek()

pq.peek();

The smallest element is always at the root (array index 0). Therefore peek() → O(1). No restructuring is necessary.

#poll() and Sift-Down

This is one of the most important PriorityQueue questions.

poll() removes 10. The last element (50) is moved to the root:

Java performs sift down: swap with the smaller child until the heap property is restored.

Therefore poll() → O(log n).

#Complexity Table

The key operations: peek → O(1), offer → O(log n), poll → O(log n).

#Iteration Is Not Sorted

Important Trap

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

pq.offer(30);
pq.offer(10);
pq.offer(20);
pq.offer(5);

Don't assume this prints 5, 10, 20, 30:

for (Integer x : pq) {
    System.out.println(x);
}

It is not guaranteed to iterate in sorted order. The heap guarantees the correct head, not sorted iteration.

How to Get Elements in Priority Order

Use repeated poll():

while (!pq.isEmpty()) {
    System.out.println(pq.poll());
}

5
10
20
30

PriorityQueue vs Sorted Collection

Don't confuse PriorityQueue with TreeSet. PriorityQueue guarantees the highest-priority element at the head; it does not maintain all elements in globally sorted iteration order. TreeSet maintains sorted ordering of its elements.

#PriorityQueue vs TreeSet

Use PriorityQueue when you mainly care about repeatedly processing the next highest-priority item.

#Custom Priority

Reverse Order — Max-Heap

By default the smallest element has the highest priority, but you can reverse it:

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

Now repeated poll() returns 50, 40, 30, 20, 10 — the largest number has the highest priority. This effectively creates a max-priority queue.

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

maxHeap.offer(10);
maxHeap.offer(50);
maxHeap.offer(20);

System.out.println(maxHeap.poll());

50

Custom Objects

class Task {
    int priority;
    String name;

    Task(int priority, String name) {
        this.priority = priority;
        this.name = name;
    }
}

PriorityQueue<Task> tasks = new PriorityQueue<>(Comparator.comparingInt(t -> t.priority));

tasks.offer(new Task(3, "Email"));
tasks.offer(new Task(1, "Payment"));
tasks.offer(new Task(2, "Report"));

Processing order (assuming a smaller priority number means higher priority):

Payment
Report
Email

Multiple Sorting Conditions

A very common interview requirement: order by priority, and if the priority is the same, by timestamp.

PriorityQueue<Task> queue = new PriorityQueue<>(
        Comparator
                .comparingInt((Task t) -> t.priority)
                .thenComparing(t -> t.timestamp)
);

This allows sophisticated scheduling policies.

#Duplicates, Null and Capacity

Duplicates

Unlike Set, PriorityQueue allows duplicates:

pq.offer(10);
pq.offer(10);
pq.offer(10);

All three elements remain. This is an important difference from TreeSet.

Null Elements

PriorityQueue does not permit null:

pq.offer(null);

NullPointerException

Why? The queue needs to compare elements according to natural ordering or the supplied Comparator, and null does not have a natural ordering by itself.

Initial Capacity

PriorityQueue<Integer> pq = new PriorityQueue<>(100);

This controls the initial backing-array capacity. It does not mean 100 elements are inserted — it's simply storage capacity.

Does PriorityQueue Grow?

Yes. It uses a dynamically growing array. When the backing array becomes full: current array → grow → copy elements → continue. The exact growth strategy is implementation-specific — don't apply ArrayList's growth formula here.

#Thread Safety

PriorityQueue Is Not Thread-Safe

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

is not thread-safe. If multiple threads need concurrent priority-queue behaviour, Java provides PriorityBlockingQueue from java.util.concurrent.

PriorityBlockingQueue

BlockingQueue<Task> queue = new PriorityBlockingQueue<>();

It combines priority ordering + BlockingQueue semantics.

#Real-World Use Cases

#Top-K Problems

Extremely important for coding interviews.

Top-K Largest Example

Input 10, 40, 20, 50, 30; need the top 3 largest. A common strategy is to maintain a min-heap of size K:

• Process elements one by one.
• If the new element is larger than the smallest heap element: remove the smallest, insert the new element.
• At the end, the heap contains the top 3 candidates.

Complexity: O(n log k) — much better than sorting all n elements when k is small.

Why a Min-Heap for Top-K Largest?

Suppose K = 3 and we currently keep 50, 40, 30. The smallest among our current top 3 is 30. If 45 arrives: 45 > 30, so remove 30 and insert 45 → now 50, 45, 40.

The root always represents the weakest member of the current Top-K set, which makes replacement efficient.

Coding Pattern — K Largest Elements

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

for (int n : numbers) {
    minHeap.offer(n);
    if (minHeap.size() > k) {
        minHeap.poll();
    }
}

// minHeap now contains the K largest elements

Complexity O(n log k), space O(k). This is an extremely useful pattern to remember.

Coding Pattern — K Smallest Elements

Use a max-heap of size K. The largest among the current K smallest elements stays at the root. If a smaller value arrives, remove the largest and insert the smaller one. Complexity O(n log k) — the opposite of the Top-K Largest pattern.

#PriorityQueue vs ArrayDeque vs LinkedList

PriorityQueue vs ArrayDeque

PriorityQueue vs LinkedList

Choose based on ordering requirements.

#Decision Framework

Final Mental Model

The three operations to memorize: peek() → O(1), offer() → O(log n), poll() → O(log n).