Priority Queue in Java – How to Use and Implement
Priority queues are one of those data structures that sound fancy but become absolutely essential once you understand their power. Whether you’re building a task scheduler, implementing Dijkstra’s algorithm, or managing event processing in high-throughput applications, priority queues let you efficiently retrieve elements based on their priority rather than insertion order. Java’s built-in PriorityQueue class makes this surprisingly straightforward, though like most powerful tools, it has its quirks and gotchas that can trip you up if you’re not careful.
How Priority Queues Work Under the Hood
Java’s PriorityQueue is built on top of a binary heap data structure, specifically a min-heap by default. This means the smallest element (according to natural ordering or a custom comparator) always sits at the front of the queue. The heap property ensures that parent nodes are always smaller than their children, making retrieval of the minimum element an O(1) operation.
The underlying array-based implementation starts with an initial capacity of 11 elements and grows dynamically when needed. Insertion operations are O(log n) because elements need to “bubble up” to maintain heap order, while removal is also O(log n) due to the “bubble down” process that restores heap integrity.
Here’s what makes PriorityQueue different from regular queues:
- Elements are ordered by priority, not insertion sequence
- Null elements are not permitted
- Iterator traversal doesn’t guarantee any particular order
- Not thread-safe (use PriorityBlockingQueue for concurrent access)
- Implements Queue interface but violates FIFO ordering
Step-by-Step Implementation Guide
Let’s start with basic usage and build up to more complex scenarios. The simplest case uses natural ordering for comparable elements:
import java.util.PriorityQueue;
import java.util.Queue;
public class BasicPriorityQueue {
public static void main(String[] args) {
Queue<Integer> pq = new PriorityQueue<>();
// Add elements in random order
pq.offer(30);
pq.offer(10);
pq.offer(50);
pq.offer(20);
// Poll elements - they come out in sorted order
while (!pq.isEmpty()) {
System.out.println(pq.poll()); // Outputs: 10, 20, 30, 50
}
}
}
For custom objects, you’ll need to implement Comparable or provide a Comparator. Here’s a practical example using a Task class:
import java.util.PriorityQueue;
import java.util.Comparator;
class Task {
private String name;
private int priority;
private long timestamp;
public Task(String name, int priority) {
this.name = name;
this.priority = priority;
this.timestamp = System.currentTimeMillis();
}
// Getters
public String getName() { return name; }
public int getPriority() { return priority; }
public long getTimestamp() { return timestamp; }
@Override
public String toString() {
return String.format("Task{name='%s', priority=%d}", name, priority);
}
}
public class TaskScheduler {
private PriorityQueue<Task> taskQueue;
public TaskScheduler() {
// Higher priority numbers = higher priority
// If priorities are equal, older tasks come first
this.taskQueue = new PriorityQueue<>(
Comparator.comparingInt(Task::getPriority).reversed()
.thenComparing(Task::getTimestamp)
);
}
public void addTask(Task task) {
taskQueue.offer(task);
System.out.println("Added: " + task);
}
public Task getNextTask() {
return taskQueue.poll();
}
public static void main(String[] args) throws InterruptedException {
TaskScheduler scheduler = new TaskScheduler();
scheduler.addTask(new Task("Low priority task", 1));
Thread.sleep(10); // Ensure different timestamps
scheduler.addTask(new Task("Critical task", 5));
Thread.sleep(10);
scheduler.addTask(new Task("Another critical task", 5));
scheduler.addTask(new Task("Medium task", 3));
System.out.println("\nProcessing tasks:");
while (scheduler.taskQueue.size() > 0) {
System.out.println("Processing: " + scheduler.getNextTask());
}
}
}
Real-World Use Cases and Examples
Priority queues shine in several practical scenarios. Here are some battle-tested implementations:
CPU Process Scheduling
class Process {
private String id;
private int priority;
private int burstTime;
private int arrivalTime;
public Process(String id, int priority, int burstTime, int arrivalTime) {
this.id = id;
this.priority = priority;
this.burstTime = burstTime;
this.arrivalTime = arrivalTime;
}
// Getters...
public String getId() { return id; }
public int getPriority() { return priority; }
public int getBurstTime() { return burstTime; }
public int getArrivalTime() { return arrivalTime; }
}
public class CPUScheduler {
private PriorityQueue<Process> readyQueue;
public CPUScheduler() {
// Shortest job first, then highest priority
this.readyQueue = new PriorityQueue<>(
Comparator.comparingInt(Process::getBurstTime)
.thenComparingInt(Process::getPriority)
);
}
public void scheduleProcess(Process process) {
readyQueue.offer(process);
}
public Process getNextProcess() {
return readyQueue.poll();
}
}
Event-Driven Simulation
class Event {
private double time;
private String type;
private Object data;
public Event(double time, String type, Object data) {
this.time = time;
this.type = type;
this.data = data;
}
public double getTime() { return time; }
public String getType() { return type; }
public Object getData() { return data; }
}
public class DiscreteEventSimulator {
private PriorityQueue<Event> eventQueue;
private double currentTime;
public DiscreteEventSimulator() {
this.eventQueue = new PriorityQueue<>(Comparator.comparingDouble(Event::getTime));
this.currentTime = 0.0;
}
public void scheduleEvent(Event event) {
if (event.getTime() >= currentTime) {
eventQueue.offer(event);
}
}
public void runSimulation(double endTime) {
while (!eventQueue.isEmpty() && currentTime < endTime) {
Event event = eventQueue.poll();
currentTime = event.getTime();
processEvent(event);
}
}
private void processEvent(Event event) {
System.out.printf("Time %.2f: Processing %s event%n",
event.getTime(), event.getType());
// Handle specific event types here
}
}
Performance Analysis and Comparisons
Understanding when to use PriorityQueue versus alternatives is crucial for performance-critical applications:
| Operation | PriorityQueue | TreeSet | ArrayList (sorted) | LinkedList |
|---|---|---|---|---|
| Insert | O(log n) | O(log n) | O(n) | O(n) |
| Remove Min | O(log n) | O(log n) | O(1) | O(n) |
| Peek Min | O(1) | O(log n) | O(1) | O(n) |
| Search | O(n) | O(log n) | O(log n) | O(n) |
| Memory | Compact | Higher overhead | Compact | Higher overhead |
Here’s a benchmark comparing insertion and removal performance:
import java.util.*;
public class PriorityQueueBenchmark {
public static void main(String[] args) {
int[] sizes = {1000, 10000, 100000};
for (int size : sizes) {
System.out.println("Testing with " + size + " elements:");
// PriorityQueue test
long start = System.nanoTime();
PriorityQueue<Integer> pq = new PriorityQueue<>();
Random rand = new Random();
for (int i = 0; i < size; i++) {
pq.offer(rand.nextInt(size * 10));
}
while (!pq.isEmpty()) {
pq.poll();
}
long end = System.nanoTime();
System.out.printf("PriorityQueue: %.2f ms%n", (end - start) / 1_000_000.0);
// TreeSet comparison
start = System.nanoTime();
TreeSet<Integer> ts = new TreeSet<>();
rand = new Random(); // Reset with same seed for fairness
for (int i = 0; i < size; i++) {
ts.add(rand.nextInt(size * 10));
}
while (!ts.isEmpty()) {
ts.pollFirst();
}
end = System.nanoTime();
System.out.printf("TreeSet: %.2f ms%n%n", (end - start) / 1_000_000.0);
}
}
}
Common Pitfalls and Best Practices
Even experienced developers can stumble with PriorityQueue. Here are the most frequent issues and how to avoid them:
Iterator Order Confusion
This is probably the biggest gotcha – the iterator doesn’t return elements in priority order:
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.addAll(Arrays.asList(30, 10, 50, 20));
System.out.println("Iterator order (WRONG for priority):");
for (Integer num : pq) {
System.out.print(num + " "); // Might print: 10 20 50 30
}
System.out.println("\nCorrect priority order:");
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " "); // Prints: 10 20 30 50
}
Mutability Issues
Modifying objects after insertion breaks heap invariants:
class MutableTask implements Comparable<MutableTask> {
private String name;
private int priority;
public MutableTask(String name, int priority) {
this.name = name;
this.priority = priority;
}
public void setPriority(int priority) {
this.priority = priority; // DANGEROUS!
}
@Override
public int compareTo(MutableTask other) {
return Integer.compare(this.priority, other.priority);
}
@Override
public String toString() {
return name + "(" + priority + ")";
}
}
// DON'T DO THIS:
public class BrokenPriorityQueue {
public static void main(String[] args) {
PriorityQueue<MutableTask> pq = new PriorityQueue<>();
MutableTask task1 = new MutableTask("Task1", 5);
MutableTask task2 = new MutableTask("Task2", 1);
pq.offer(task1);
pq.offer(task2);
System.out.println("Before mutation: " + pq.poll()); // Task2(1)
// Restore task2 and mutate task1
pq.offer(task2);
task1.setPriority(0); // This breaks the heap!
System.out.println("After mutation: " + pq.poll()); // Might not be Task1!
}
}
Thread Safety
PriorityQueue is not thread-safe. For concurrent access, use PriorityBlockingQueue:
import java.util.concurrent.PriorityBlockingQueue;
public class ThreadSafePriorityQueue {
private PriorityBlockingQueue<Task> taskQueue;
public ThreadSafePriorityQueue() {
this.taskQueue = new PriorityBlockingQueue<>(11,
Comparator.comparingInt(Task::getPriority).reversed()
);
}
public void addTask(Task task) {
taskQueue.put(task); // Blocks if queue is full (though PBQ is unbounded)
}
public Task getNextTask() throws InterruptedException {
return taskQueue.take(); // Blocks if queue is empty
}
}
Advanced Techniques and Optimizations
For high-performance scenarios, consider these optimization strategies:
Custom Initial Capacity
// Avoid repeated array resizing for known workloads
PriorityQueue<Integer> pq = new PriorityQueue<>(10000);
Batch Operations
// More efficient than multiple individual offers
List<Integer> batch = Arrays.asList(5, 2, 8, 1, 9);
PriorityQueue<Integer> pq = new PriorityQueue<>(batch);
Memory-Conscious Comparators
// Avoid boxing/unboxing in hot paths
Comparator<Task> efficientComparator = (t1, t2) -> {
int result = Integer.compare(t2.getPriority(), t1.getPriority());
if (result == 0) {
result = Long.compare(t1.getTimestamp(), t2.getTimestamp());
}
return result;
};
For more advanced usage and implementation details, check out the official Java PriorityQueue documentation and the Java Collections Tutorial.
Priority queues might seem like a niche data structure, but once you start recognizing the patterns where they apply, you’ll find them everywhere. From managing server request priorities to implementing pathfinding algorithms, they’re an essential tool in any developer’s toolkit. Just remember the golden rules: don’t mutate elements after insertion, don’t rely on iterator ordering, and use PriorityBlockingQueue when threads are involved.
This article incorporates information and material from various online sources. We acknowledge and appreciate the work of all original authors, publishers, and websites. While every effort has been made to appropriately credit the source material, any unintentional oversight or omission does not constitute a copyright infringement. All trademarks, logos, and images mentioned are the property of their respective owners. If you believe that any content used in this article infringes upon your copyright, please contact us immediately for review and prompt action.
This article is intended for informational and educational purposes only and does not infringe on the rights of the copyright owners. If any copyrighted material has been used without proper credit or in violation of copyright laws, it is unintentional and we will rectify it promptly upon notification. Please note that the republishing, redistribution, or reproduction of part or all of the contents in any form is prohibited without express written permission from the author and website owner. For permissions or further inquiries, please contact us.
More stories
