Priority Queue

Imagine a hospital emergency room. Patients don't always get treated in the order they arrive. Instead, patients with more serious conditions are treated first.

For example:

Patient A → Priority 2
Patient B → Priority 10
Patient C → Priority 5

The processing order could be:

Patient B
Patient C
Patient A

The patient with the highest priority is processed first.

This is the basic idea behind a Priority Queue.

A priority queue is a data structure where each element has a priority, and the element with the highest priority is processed before elements with lower priority.

In Java, PriorityQueue is commonly implemented using a heap.

What is a Priority Queue?

A normal queue follows:

First In → First Out

For example:

10 → 20 → 30 → 40

If 10 enters first, it leaves first.

A priority queue works differently.

Instead of simply considering insertion order, it considers priority.

For example:

10 → Priority 5
20 → Priority 2
30 → Priority 8

The element with priority 8 may be processed first:

30 → 10 → 20

So:

Queue:
First In, First Out

Priority Queue:
Highest/Lowest Priority First

Priority Queue and Heap

A priority queue is an abstract data structure, while a heap is a common data structure used to implement it efficiently.

Think of it like this:

Priority Queue
      ↓
Implementation
      ↓
Heap

In Java:

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

By default, Java's PriorityQueue behaves like a Min Heap.

That means the smallest element has the highest priority.

Creating a Priority Queue in Java

First, import it:

import java.util.PriorityQueue;

Then:

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

Now we can add numbers:

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

The smallest element has priority.

10 → Highest priority
20
30

Adding Elements

We can add elements using:

add()

or:

offer()

For example:

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

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

The priority queue internally organizes the elements so that the highest-priority element can be accessed efficiently.

add() vs offer()

Both can insert an element:

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

For normal use with Java's PriorityQueue, both are commonly used.

The main difference comes from the general Queue interface:

add()   → may throw an exception if insertion fails
offer() → returns false if insertion fails

For PriorityQueue, capacity isn't normally a concern because it grows dynamically.

Viewing the Highest-Priority Element

We can use:

peek()

For example:

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

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

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

Output:

10

The smallest element is at the top because Java's default PriorityQueue is a Min Heap.

Important:

peek() does not remove the element.

The queue remains unchanged.

Removing the Highest-Priority Element

Use:

poll()

For example:

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

Output:

10

Now 10 is removed.

The next smallest element becomes the highest-priority element:

20

So:

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

prints:

20

Then:

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

prints:

30

peek() vs poll()

This is important to remember:

peek() → View the top element
poll() → Remove and return the top element

For example:

queue.peek();

doesn't remove anything.

But:

queue.poll();

removes the element.

What Happens When the Queue Is Empty?

Suppose:

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

and we call:

queue.peek();

The result is:

null

Similarly:

queue.poll();

returns:

null

when the queue is empty.

You can check whether the queue is empty using:

queue.isEmpty();

Min Priority Queue

By default, Java creates a Min Priority Queue.

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

Suppose we add:

minHeap.add(50);
minHeap.add(10);
minHeap.add(30);
minHeap.add(20);

The highest-priority element is the smallest value:

10

So:

System.out.println(minHeap.peek());

outputs:

10

If we repeatedly remove elements:

while (!minHeap.isEmpty()) {
    System.out.print(minHeap.poll() + " ");
}

Output:

10 20 30 50

Max Priority Queue

Sometimes we want the largest element to have the highest priority.

For that, we can create a Max Priority Queue using a comparator.

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

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

Now:

maxHeap.add(50);
maxHeap.add(10);
maxHeap.add(30);
maxHeap.add(20);

The highest-priority element is:

50

So:

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

outputs:

50

If we repeatedly remove elements:

while (!maxHeap.isEmpty()) {
    System.out.print(maxHeap.poll() + " ");
}

Output:

50 30 20 10

So:

Min Priority Queue → Smallest first
Max Priority Queue → Largest first

Priority Queue Example

Suppose we have tasks:

Task A → Priority 3
Task B → Priority 1
Task C → Priority 5
Task D → Priority 2

If a larger number means higher priority, we can use a Max Heap.

The processing order would be:

Task C → 5
Task A → 3
Task D → 2
Task B → 1

This is different from a normal queue.

A normal queue would process based on arrival order.

Priority Queue with Custom Objects

Priority queues become much more useful when each element has multiple pieces of information.

For example, suppose we have a Task class:

class Task {
    String name;
    int priority;

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

Now suppose we want tasks with higher priority to come first.

We can create:

PriorityQueue<Task> tasks =
    new PriorityQueue<>(
        (a, b) -> Integer.compare(
            b.priority,
            a.priority
        )
    );

Then add tasks:

tasks.add(new Task("Email", 2));
tasks.add(new Task("Deploy App", 10));
tasks.add(new Task("Meeting", 5));

Now:

Task task = tasks.poll();

System.out.println(task.name);

Output:

Deploy App

because it has priority 10.

Why Use a Comparator?

Java needs to know how to compare custom objects.

For integers, Java already knows how to compare:

10 < 20

But if we have:

Task

Java needs to know whether priority 10 should come before priority 5.

That's what the comparator tells it.

For example:

(a, b) -> Integer.compare(
    b.priority,
    a.priority
)

means higher priority comes first.

Priority Queue for Students

Suppose students have marks:

John → 75
Alex → 90
Jason → 82

If we want the student with the highest marks first:

class Student {
    String name;
    int marks;

    Student(String name, int marks) {
        this.name = name;
        this.marks = marks;
    }
}

Create the priority queue:

PriorityQueue<Student> students =
    new PriorityQueue<>(
        (a, b) -> Integer.compare(
            b.marks,
            a.marks
        )
    );

Add students:

students.add(
    new Student("John", 75)
);

students.add(
    new Student("Alex", 90)
);

students.add(
    new Student("Jason", 82)
);

Now:

Student top = students.poll();

System.out.println(top.name);

Output:

Alex

because Alex has the highest marks.

Priority Queue for DSA Problems

Priority queues appear frequently in DSA.

Suppose you have:

[5, 1, 9, 3, 7]

and want to repeatedly find the smallest element.

Instead of repeatedly searching through the entire array, we can put everything into a Min Heap:

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

for (int number : numbers) {
    pq.add(number);
}

Then:

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

gives:

1
3
5
7
9

Finding the K Largest Elements

One very common DSA problem is:

Find the K largest elements in an array.

For example:

[10, 4, 7, 2, 15, 8]

Suppose:

K = 3

The answer is:

15, 10, 8

A priority queue can solve this efficiently.

One common approach is to maintain a Min Heap of size K.

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

for (int number : numbers) {

    pq.add(number);

    if (pq.size() > k) {
        pq.poll();
    }
}

After processing all elements, the heap contains the K largest values.

This is a very important heap pattern.

Finding the K Smallest Elements

We can reverse the idea.

To find the K smallest elements, we can maintain a Max Heap of size K.

For example:

[10, 4, 7, 2, 15, 8]

For:

K = 3

we want:

2, 4, 7

A Max Heap lets us remove the largest element whenever our heap becomes larger than K.

Priority Queue in Dijkstra's Algorithm

Priority queues are heavily used in graph algorithms.

One famous example is Dijkstra's shortest path algorithm.

Suppose we have:

A → B = 4
A → C = 2
C → B = 1

Dijkstra's algorithm repeatedly needs to select the unprocessed node with the smallest known distance.

A Min Priority Queue is perfect for this.

Conceptually:

Node → Distance

A → 0
B → 4
C → 2

The priority queue gives:

A
C
B

based on the smallest distance.

This allows Dijkstra's algorithm to efficiently select the next most promising node.

Priority Queue in Prim's Algorithm

Priority queues are also commonly used in Prim's Minimum Spanning Tree algorithm.

At each step, we need to select the smallest edge that can extend the current tree.

A Min Heap makes this efficient.

So you will frequently see:

Priority Queue
      ↓
Graph Algorithms
      ↓
Dijkstra
Prim

Priority Queue vs Normal Queue

This distinction is extremely important.

Suppose elements arrive in this order:

A
B
C

Normal Queue

Processing order:

A
B
C

because it follows FIFO.

Priority Queue

Suppose:

A → Priority 2
B → Priority 10
C → Priority 5

Processing order:

B
C
A

because priority determines the order.

So:

Queue:
Arrival order matters

Priority Queue:
Priority matters

Priority Queue vs Stack

A stack follows:

LIFO

For:

A
B
C

the last inserted element comes out first:

C
B
A

A priority queue doesn't care about simply being the last inserted.

It chooses according to priority.

Stack:
Last inserted → First out

Priority Queue:
Highest/lowest priority → First out

Priority Queue vs HashMap

A HashMap is designed for key-value lookup:

Key → Value

A priority queue is designed to repeatedly access the highest- or lowest-priority element.

For example:

HashMap:
101 → John
102 → Alex

versus:

PriorityQueue:
10
20
30

where the smallest or largest value can be prioritized.

Time Complexity

For Java's heap-based PriorityQueue, the important complexities are:

The reason insertion and removal are O(log n) is that the underlying heap may need to move an element up or down the tree.

The root can be accessed directly, so peek() is O(1).

Important: PriorityQueue Is Not Fully Sorted

This is a common mistake.

Suppose:

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

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

You might think the internal queue is:

10 20 30 50

But you should not assume that iterating over the PriorityQueue produces sorted order.

For example:

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

does not guarantee sorted output.

If you want elements in priority order, repeatedly use:

poll()

For example:

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

This gives:

10 20 30 50

A Complete Java Example

Let's build a task scheduler where higher-priority tasks are processed first:

import java.util.PriorityQueue;

class Task {
    String name;
    int priority;

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

class Main {

    public static void main(String[] args) {

        PriorityQueue<Task> tasks =
            new PriorityQueue<>(
                (a, b) ->
                    Integer.compare(
                        b.priority,
                        a.priority
                    )
            );

        tasks.add(
            new Task("Check Email", 2)
        );

        tasks.add(
            new Task("Fix Production Bug", 10)
        );

        tasks.add(
            new Task("Team Meeting", 5)
        );

        tasks.add(
            new Task("Write Documentation", 3)
        );

        while (!tasks.isEmpty()) {

            Task task = tasks.poll();

            System.out.println(
                task.name +
                " → Priority " +
                task.priority
            );
        }
    }
}

Output:

Fix Production Bug → Priority 10
Team Meeting → Priority 5
Write Documentation → Priority 3
Check Email → Priority 2

The priority queue automatically gives us the most important task first.

Real-Life Applications

Priority queues are useful whenever things need to be processed based on importance.

Hospital Emergency Room

Critical patient
      ↓
High priority
      ↓
Treated first

CPU Scheduling

High-priority process
      ↓
CPU

Network Routing

Packets or tasks can be processed according to priority.

Dijkstra's Algorithm

The node with the smallest known distance is selected first.

Prim's Algorithm

The smallest suitable edge is selected first.

Event Scheduling

The next event can be selected based on its scheduled time.

Top-K Problems

Priority queues make it efficient to keep track of the largest or smallest K elements.

The Main Idea

A Priority Queue is a data structure where elements are processed according to their priority, rather than simply their insertion order.

The most important Java methods are:

add()    → Insert
offer()  → Insert
peek()   → View highest-priority element
poll()   → Remove highest-priority element
isEmpty() → Check whether empty
size()   → Number of elements

Java's default:

PriorityQueue
      ↓
Min Heap
      ↓
Smallest element has highest priority

For a Max Priority Queue:

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

The key complexity is:

peek() → O(1)
add()  → O(log n)
poll() → O(log n)

And the most important relationship to remember is:

Priority Queue
      ↓
Usually implemented using
      ↓
Heap
      ↓
Efficient priority-based processing

A priority queue is ideal when you repeatedly need to process the most important, smallest, or largest element from a collection.

Once you understand Priority Queue, you'll start seeing it everywhere in DSA—especially in Top-K problems, scheduling, Dijkstra's algorithm, Prim's algorithm, and heap-based problems.