PriorityQueue in Java

Process elements based on priority, not arrival order.

Imagine you’re building a Hospital Management System where patients are waiting to be treated. Treating patients strictly in the order they arrive may not always be appropriate. A critical patient may need immediate attention even if they arrived after several other patients.

A similar situation occurs in software systems. Some tasks are more important than others and should be processed first. A normal FIFO Queue cannot handle this requirement because it processes elements based primarily on their arrival order.

This is where PriorityQueue becomes useful.

PriorityQueue is a queue implementation in Java that processes elements according to their priority rather than strictly following insertion order. By default, elements are ordered according to their natural ordering, while a custom Comparator can be provided when a different priority rule is required.

---

What is PriorityQueue?

PriorityQueue is a class in the Java Collections Framework that implements the Queue interface.

Unlike a traditional FIFO queue, the element at the head of a PriorityQueue is the highest-priority element according to its ordering.

By default, the smallest element has the highest priority.

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

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

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

Output:

10

Although 30 was inserted first, 10 is removed first because it has the highest priority according to the natural ordering.

---

Why Do We Need PriorityQueue?

A normal queue works well when every element should be processed in arrival order.

But consider a task scheduling system:

Task A → Low Priority
Task B → High Priority
Task C → Medium Priority

If these tasks are placed in a normal FIFO queue, Task A would be processed first.

With a PriorityQueue, the application can process the highest-priority task first.

High Priority
      ↓
Task B
      ↓
Medium Priority
      ↓
Task C
      ↓
Low Priority
      ↓
Task A

This makes PriorityQueue useful when processing order depends on priority rather than simply on arrival time.

---

How Does PriorityQueue Work?

Internally, Java’s PriorityQueue is implemented using a priority heap, specifically a binary heap.

By default, it behaves as a min-heap, meaning the smallest element is maintained at the head.

Consider:

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

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

Conceptually, the heap maintains the smallest element at the top:

        10
       /  \
     20    30
    /
   40

The internal structure is optimized for efficiently finding and removing the highest-priority element.

One important point is that the internal heap is not a fully sorted collection. Only the head is guaranteed to be the highest-priority element according to the queue’s ordering.

---

Creating a PriorityQueue

The simplest way to create one is:

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

By default, elements are ordered according to their natural ordering.

For example:

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

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

The next element returned by poll() will be:

10

---

PriorityQueue with Custom Comparator

Sometimes the smallest value should not have the highest priority.

For example, suppose we want the largest number to be processed first.

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

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

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

Output:

50

A Comparator allows us to define our own priority rules.

---

PriorityQueue with Custom Objects

PriorityQueue becomes particularly useful when working with custom objects.

Suppose we have a Task class:

class Task {
    String name;
    int priority;

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

We can create a queue based on task priority:

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

Now the task with the smallest priority value will be processed first.

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

The payment task will be processed first because it has the highest priority according to our defined ordering.

---

Common Methods

offer()

Adds an element to the priority queue.

queue.offer(20);

For a PriorityQueue, insertion generally takes O(log n) time.

---

poll()

Retrieves and removes the highest-priority element.

queue.poll();

For the default min-heap, this removes the smallest element.

---

peek()

Retrieves the highest-priority element without removing it.

queue.peek();

This operation takes O(1) time.

---

remove()

Removes the head element.

queue.remove();

Removing the head generally takes O(log n) time.

---

size()

Returns the number of elements.

queue.size();

---

isEmpty()

Checks whether the queue contains any elements.

queue.isEmpty();

---

PriorityQueue Time Complexity

The main operations have different complexities because the queue must maintain its heap structure.

offer() and add() generally take O(log n) because the newly inserted element may need to move upward to maintain the heap property.

poll() and removing the head also take O(log n) because the heap must be reorganized after removal. peek() takes O(1) because the highest-priority element is always available at the head.

Operations such as contains() and removing an arbitrary object take O(n) because the heap does not provide efficient searching for arbitrary elements.

---

PriorityQueue vs Queue

A normal FIFO queue generally processes elements according to their arrival order.

A PriorityQueue, however, processes elements according to their priority.

For example:

Normal Queue:

10 → 30 → 20
↓
10 is removed first

With a default PriorityQueue:

10 → 30 → 20
↓
10 is the highest priority

Now consider:

30 → 10 → 20

A normal queue removes:

30

But a default PriorityQueue removes:

10

because it uses natural ordering rather than insertion order.

---

PriorityQueue vs ArrayDeque

Both PriorityQueue and ArrayDeque implement the Queue interface, but they solve different problems.

ArrayDeque is suitable when you need efficient FIFO queue operations or double-ended operations. PriorityQueue should be used when elements need to be processed according to priority.

In simple terms:

Use ArrayDeque for order of arrival.

Use PriorityQueue for order of priority.

Choosing between them should depend on the actual processing requirement rather than simply their common Queue interface.

---

Does PriorityQueue Maintain Sorted Order?

This is one of the most common misconceptions about PriorityQueue.

The answer is No.

A PriorityQueue does not guarantee that iterating over it will produce elements in sorted order.

For example:

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

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

for (Integer number : queue) {
    System.out.println(number);
}

The iteration order is not guaranteed to be:

10
20
30
40

However, repeatedly calling poll() will retrieve elements according to the queue’s ordering.

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

Output:

10
20
30
40

If you need a collection that maintains all elements in sorted order, a TreeSet or another appropriate sorted collection may be a better choice.

---

Does PriorityQueue Allow Duplicates?

Yes.

Unlike Set implementations such as HashSet and TreeSet, PriorityQueue allows duplicate elements.

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

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

System.out.println(queue.size());

Output:

3

Both 10 values are stored.

---

Can PriorityQueue Store null?

No.

A PriorityQueue does not permit null elements because it needs to compare elements to maintain its ordering.

queue.offer(null);

This results in a NullPointerException.

---

Real-World Applications

PriorityQueue is useful whenever tasks need to be processed according to priority.

Common examples include:

• Task Scheduling

• Hospital Emergency Systems

• CPU Scheduling

• Network Packet Processing

• Event Processing

• Job Scheduling

• Dijkstra’s Algorithm

• A* Search

• Huffman Coding

• Top-K Problems

For example, shortest-path algorithms such as Dijkstra’s Algorithm commonly use a priority queue to efficiently select the next node with the smallest known distance.

---

PriorityQueue in Backend Applications

Priority-based processing is also useful in backend systems.

Imagine an application receiving different types of background tasks:

Payment Processing    → Priority 1
Security Alert        → Priority 1
Email Notification    → Priority 3
Report Generation     → Priority 5

Instead of processing tasks strictly according to arrival time, workers can prioritize critical operations.

             Tasks
               ↓
        PriorityQueue
               ↓
       Highest Priority
               ↓
            Worker

This basic concept is useful for understanding more advanced task scheduling and messaging systems.

However, Java’s PriorityQueue is an in-memory data structure. It is not a replacement for distributed messaging systems such as Kafka or RabbitMQ when persistence, scalability, or communication between independent services is required.

---

Best Practices

• Use PriorityQueue when processing order depends on priority.

• Use a Comparator when the default natural ordering is not appropriate.

• Remember that iteration does not guarantee sorted order.

• Use peek() when you only need to inspect the highest-priority element.

• Use poll() when you need to retrieve and remove it.

• Don’t insert null values.

• Prefer immutable or stable fields for priority comparisons in custom objects.

• Don’t use PriorityQueue when simple FIFO processing is sufficient.

---

Common Interview Questions

What is PriorityQueue?

PriorityQueue is a Queue implementation that processes elements according to their priority rather than strictly following insertion order.

Is PriorityQueue FIFO?

No.

It processes elements according to its ordering rules.

What is the default ordering?

Natural ordering, with the smallest element at the head.

Which data structure is used internally?

A binary heap, implemented using an array-based structure.

What is the time complexity of offer()?

O(log n).

What is the time complexity of peek()?

O(1).

Does PriorityQueue allow duplicates?

Yes.

Does PriorityQueue allow null?

No.

Does PriorityQueue maintain sorted order during iteration?

No.

Only the head is guaranteed to have the highest priority according to the queue’s ordering.

---

Common Mistakes Developers Make

A common mistake is assuming that PriorityQueue is simply a sorted queue. It is not. The internal heap guarantees efficient access to the highest-priority element, but iteration does not guarantee sorted order.

Another mistake is assuming that the first element inserted will always be removed first. That is true for a normal FIFO queue, but not for PriorityQueue. The element with the highest priority according to the queue’s ordering is removed first.

Developers also sometimes forget that custom objects require a meaningful ordering. When using custom objects, you should provide a suitable Comparator or ensure the objects have an appropriate natural ordering.

---

Conclusion

PriorityQueue is a powerful Java collection for situations where priority matters more than arrival order. Unlike a traditional FIFO queue, it uses a heap-based structure to efficiently identify and remove the highest-priority element.

Its O(log n) insertion and removal operations and O(1) head access make it useful for scheduling, graph algorithms, event processing, and many other priority-based problems.

The most important thing to remember is:

Queue → Process based on arrival order.
PriorityQueue → Process based on priority.

Understanding this distinction will help you choose the right collection and solve many common Java interview problems.

In the next article, we’ll explore Deque in Java and understand how elements can be added and removed from both ends of a collection.