Java PriorityQueue
PriorityQueue is a Queue implementation in Java that processes elements according to their priority rather than simply processing them in insertion order.
By default, elements are ordered according to their natural ordering.
For example, with integers, the smallest value has the highest priority.
import java.util.PriorityQueue;
public class HelloWorld {
public static void main(String[] args) {
PriorityQueue<Integer> numbers = new PriorityQueue<>();
numbers.offer(50);
numbers.offer(10);
numbers.offer(30);
numbers.offer(20);
System.out.println(numbers.poll());
}
}Output
10Although 50 was added first, 10 is processed first because it has the highest priority according to the queue's natural ordering.
Why Do We Need PriorityQueue?
A normal FIFO queue processes elements based mainly on arrival order.
For example:
A → B → C → DA PriorityQueue instead processes elements according to their priority.
For numbers using natural ordering:
50
10
30
20The processing order is:
10 → 20 → 30 → 50This is useful when the most important or highest-priority item needs to be processed first.
Creating a PriorityQueue
PriorityQueue<Integer> queue = new PriorityQueue<>();We can also specify an initial capacity:
PriorityQueue<Integer> queue =
new PriorityQueue<>(20);Adding Elements
Use offer():
queue.offer(40);
queue.offer(10);
queue.offer(30);You can also use:
queue.add(20);Both are supported because PriorityQueue implements Queue.
Retrieving the Highest-Priority Element
Use:
queue.peek();It returns the head without removing it.
Example
PriorityQueue<Integer> numbers = new PriorityQueue<>();
numbers.offer(50);
numbers.offer(10);
numbers.offer(30);
System.out.println(numbers.peek());Output
10The queue remains unchanged.
Removing the Highest-Priority Element
Use:
queue.poll();Example
System.out.println(queue.poll());The smallest element is returned for the natural ordering of integers.
Processing All Elements
A common pattern is:
while (!queue.isEmpty()) {
System.out.println(queue.poll());
}Example
PriorityQueue<Integer> numbers = new PriorityQueue<>();
numbers.offer(50);
numbers.offer(10);
numbers.offer(30);
numbers.offer(20);
while (!numbers.isEmpty()) {
System.out.println(numbers.poll());
}Output
10
20
30
50Important: PriorityQueue Iteration Is Not Sorted Order
This is an important point.
Consider:
PriorityQueue<Integer> numbers = new PriorityQueue<>();
numbers.offer(50);
numbers.offer(10);
numbers.offer(30);
numbers.offer(20);You should not assume that:
for (Integer number : numbers) {
System.out.println(number);
}will print:
10
20
30
50The iterator does not guarantee sorted traversal.
If you want to repeatedly retrieve elements according to priority, use poll():
while (!numbers.isEmpty()) {
System.out.println(numbers.poll());
}Natural Ordering
By default, PriorityQueue uses natural ordering.
For integers:
10 < 20 < 30So the smallest integer has the highest priority.
For Strings, the natural ordering of String is used.
PriorityQueue<String> queue = new PriorityQueue<>();
queue.offer("Java");
queue.offer("C++");
queue.offer("Python");
while (!queue.isEmpty()) {
System.out.println(queue.poll());
}The elements are retrieved according to their natural ordering.
Using Comparator with PriorityQueue
We can provide a Comparator to define custom priority.
For example, to process larger numbers first:
PriorityQueue<Integer> numbers =
new PriorityQueue<>(Comparator.reverseOrder());
numbers.offer(10);
numbers.offer(50);
numbers.offer(20);
numbers.offer(30);
while (!numbers.isEmpty()) {
System.out.println(numbers.poll());
}Output
50
30
20
10PriorityQueue 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 PriorityQueue using a Comparator:
PriorityQueue<Task> tasks =
new PriorityQueue<>(
Comparator.comparingInt(task -> task.priority)
);Then:
tasks.offer(new Task("Backup", 3));
tasks.offer(new Task("Payment", 1));
tasks.offer(new Task("Email", 2));The task with priority 1 will be retrieved first.
Task task = tasks.poll();PriorityQueue with Comparable
Instead of providing a Comparator, a custom class can implement Comparable.
class Task implements Comparable<Task> {
String name;
int priority;
Task(String name, int priority) {
this.name = name;
this.priority = priority;
}
@Override
public int compareTo(Task other) {
return Integer.compare(this.priority, other.priority);
}
}Now the PriorityQueue can use the class's natural ordering.
Null Elements
PriorityQueue does not permit null elements.
This causes an exception:
PriorityQueue<String> queue = new PriorityQueue<>();
queue.offer(null);Avoid adding null to a PriorityQueue.
Duplicate Elements
PriorityQueue allows duplicate elements.
PriorityQueue<Integer> numbers = new PriorityQueue<>();
numbers.offer(10);
numbers.offer(10);
numbers.offer(20);The two 10 values can both exist.
Common Methods
| Method | Purpose |
|---|---|
| offer() | Adds an element |
| add() | Adds an element |
| peek() | Reads the head |
| poll() | Removes and returns the head |
| remove() | Removes the head |
| contains() | Checks for an element |
| size() | Returns number of elements |
| isEmpty() | Checks whether queue is empty |
| clear() | Removes all elements |
PriorityQueue vs Queue
| Feature | Queue | PriorityQueue |
|---|---|---|
| Main idea | Queue processing | Priority-based processing |
| Typical FIFO behavior | Implementation dependent | No |
| Priority ordering | Implementation dependent | Yes |
| offer() | Yes | Yes |
| poll() | Yes | Yes |
| Custom ordering | Implementation dependent | Supported using Comparator |
PriorityQueue vs ArrayList
ArrayList is primarily used to store and access elements by index.
PriorityQueue is designed for repeatedly retrieving the highest-priority element.
ArrayList<Integer> numbers = new ArrayList<>();vs.
PriorityQueue<Integer> numbers = new PriorityQueue<>();Choose based on the required operation rather than simply the data type.
Practical Example: Task Priority
import java.util.PriorityQueue;
import java.util.Comparator;
class Task {
String name;
int priority;
Task(String name, int priority) {
this.name = name;
this.priority = priority;
}
}
public class HelloWorld {
public static void main(String[] args) {
PriorityQueue<Task> tasks =
new PriorityQueue<>(
Comparator.comparingInt(task -> task.priority)
);
tasks.offer(new Task("Generate Report", 3));
tasks.offer(new Task("Process Payment", 1));
tasks.offer(new Task("Send Email", 2));
while (!tasks.isEmpty()) {
Task task = tasks.poll();
System.out.println(
task.name + " - Priority " + task.priority
);
}
}
}Output
Process Payment - Priority 1
Send Email - Priority 2
Generate Report - Priority 3Performance
PriorityQueue is implemented using a priority-heap structure.
Typical complexity:
offer() → O(log n)
poll() → O(log n)
peek() → O(1)
contains() → O(n)When Should You Use PriorityQueue?
Use PriorityQueue when:
- Elements have different priorities.
- The next element should be selected according to an ordering.
- You repeatedly need the smallest or largest element.
You need priority-based task processing. Examples: Task scheduling Job processing Priority-based notifications Event processing Finding the smallest/largest elements repeatedly
Key Takeaway
PriorityQueue is a queue implementation where elements are retrieved according to their priority. Natural ordering can be used by default, while Comparator can be used to define custom priority rules.
See you in next page....🙂