PriorityQueue in Java: A Complete Guide

PriorityQueue in Java: A Complete Guide

In Java, the PriorityQueue is a powerful data structure that belongs to the java.util package and implements the Queue interface. It is part of the Java Collections Framework and provides a way to process elements based on their priority rather than the order in which they were added. Whether you’re scheduling tasks, managing queues in simulations, or handling real-time systems, PriorityQueue can be extremely useful.

This blog post will give you a comprehensive understanding of the PriorityQueue class — from its internal working and usage to examples, performance, and real-world applications.

What is a PriorityQueue?

A PriorityQueue is a queue where elements are ordered according to their natural ordering (defined by Comparable) or by a custom comparator provided at the time of creation. The head of the queue is the element with the highest priority (in natural order, the smallest element).

Key Characteristics

Implements a min-heap by default.
Elements are not ordered like a sorted collection, only the head (smallest element) is guaranteed.
Null elements are not allowed.
Unbounded, but has an internal capacity that grows automatically.
Not thread-safe (use PriorityBlockingQueue for thread-safe operations).

Creating a PriorityQueue

With Natural Ordering

import java.util.PriorityQueue;

public class NaturalPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(20);
        pq.add(5);
        pq.add(15);

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

Output:

5
15
20

With Custom Comparator

import java.util.*;

public class CustomComparatorPQ {
    public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> b.length() - a.length());
        pq.add("apple");
        pq.add("banana");
        pq.add("kiwi");

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

Output:

banana
apple
kiwi

Common Methods

Method	Description
`add(e)`	Inserts element into the queue. Throws exception if fails.
`offer(e)`	Inserts element into the queue. Returns false if fails.
`peek()`	Retrieves head of the queue without removing it.
`poll()`	Retrieves and removes the head of the queue.
`remove()`	Removes the head of the queue.
`size()`	Returns the size of the queue.
`clear()`	Removes all elements from the queue.

Internal Working

The PriorityQueue is implemented using a binary heap, which is typically represented as an array. The key properties include:

Heap invariant is maintained: the parent is always smaller than its children.
On adding elements, the heap reorders itself using the heapify-up operation.
On removal (poll), the heap performs heapify-down to maintain the structure.

PriorityQueue with Custom Objects

import java.util.*;

class Task {
    int priority;
    String name;

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

    @Override
    public String toString() {
        return name + " (Priority: " + priority + ")";
    }
}

public class TaskScheduler {
    public static void main(String[] args) {
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(Comparator.comparingInt(t -> t.priority));

        taskQueue.add(new Task(3, "Low priority task"));
        taskQueue.add(new Task(1, "High priority task"));
        taskQueue.add(new Task(2, "Medium priority task"));

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

Output:

High priority task (Priority: 1)
Medium priority task (Priority: 2)
Low priority task (Priority: 3)

Use Cases

Task Scheduling: Order tasks based on priority.
Graph Algorithms: Like Dijkstra’s shortest path algorithm.
Simulation Systems: Where events are processed based on time.
Job Queues: Handling jobs in order of importance.

Limitations

No constant-time access to arbitrary elements.
Not thread-safe for concurrent access.
Iterator does not guarantee traversal in priority order.

PriorityQueue vs Other Queues

Feature	PriorityQueue	LinkedList (Queue)	ArrayDeque
Ordering	Based on priority	Insertion order	Insertion order
Null elements	Not allowed	Allowed	Not allowed
Thread safety	No	No	No
Time complexity	Logarithmic for add/poll	Constant	Constant

Conclusion

The PriorityQueue in Java is a versatile and efficient structure for handling priority-based processing. Its implementation via a binary heap ensures efficient performance for insertion and deletion. While it may not suit all scenarios (e.g., concurrent needs or random access), it excels in task scheduling, simulations, and algorithm implementations.

Understanding how and when to use PriorityQueue allows you to write more performant and cleaner Java code, especially when handling ordered tasks or events.