The PriorityQueue class in Java is a specialized type of queue that operates on a priority-based ordering rather than the usual First-In-First-Out (FIFO) principle. It is part of the java.util package and implements the Queue interface, meaning it can be used wherever a queue is expected. Unlike regular queues, elements in a PriorityQueue are processed according to their natural ordering or based on a custom comparator, making it an essential tool for scenarios where certain elements should be given priority over others.

What is a Java PriorityQueue?

A PriorityQueue is a collection of elements where each element has a priority associated with it. The elements are processed in order of their priority, rather than the order in which they were inserted. By default, a PriorityQueue orders its elements based on their natural ordering (e.g., numbers in ascending order, strings in alphabetical order). However, you can provide a custom comparator to define how elements should be ordered.

Key Features of PriorityQueue

• Order: Elements are ordered based on their priority. The highest-priority element is always at the front.
• No Capacity Limit: The queue grows dynamically as elements are added.
• Not Thread-Safe: The PriorityQueue is not synchronized, meaning it is not suitable for concurrent access without additional synchronization mechanisms.
• Null Elements: PriorityQueue does not allow null elements and will throw a NullPointerException if you try to add one.

By default, the PriorityQueue uses natural ordering for comparison, but you can provide a custom comparator to control how elements are prioritized.

Common Methods of PriorityQueue

Here are some key methods that you can use with a PriorityQueue:

• offer(E e): Adds an element to the queue. Returns true if the element is added successfully.
• poll(): Removes and returns the element with the highest priority (the front element). Returns null if the queue is empty.
• peek(): Returns the element with the highest priority without removing it. Returns null if the queue is empty.
• remove(Object o): Removes a specific element from the queue.
• size(): Returns the number of elements in the queue.
• isEmpty(): Checks if the queue is empty.

Creating a Java PriorityQueue

The PriorityQueue class can be instantiated in different ways depending on your use case. Let's look at some examples of how to create a PriorityQueue.

Example 1: Using Default Natural Ordering

If you're working with elements that implement Comparable (e.g., Integer, String), you can create a PriorityQueue that uses the natural ordering of elements.

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        // Creating a PriorityQueue of Integers (default natural ordering: ascending order)
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        // Adding elements to the queue
        queue.offer(50);
        queue.offer(10);
        queue.offer(30);
        queue.offer(40);

        // Display the queue
        System.out.println("PriorityQueue: " + queue);
        
        // Poll the highest priority element (the smallest number)
        System.out.println("Polled Element: " + queue.poll());
        
        // Display the queue after polling
        System.out.println("PriorityQueue after poll: " + queue);
    }
}

Output:

PriorityQueue: [10, 40, 30, 50]
Polled Element: 10
PriorityQueue after poll: [30, 40, 50]

In this case, the queue is ordered in ascending order, and 10, the smallest element, is polled first.

Example 2: Using a Custom Comparator

You can also specify your own comparator to define the priority order. For example, you can create a PriorityQueue that processes elements in descending order.

import java.util.PriorityQueue;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
        // Creating a PriorityQueue of Integers (custom comparator for descending order)
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());

        // Adding elements to the queue
        queue.offer(50);
        queue.offer(10);
        queue.offer(30);
        queue.offer(40);

        // Display the queue
        System.out.println("PriorityQueue: " + queue);

        // Poll the highest priority element (the largest number)
        System.out.println("Polled Element: " + queue.poll());

        // Display the queue after polling
        System.out.println("PriorityQueue after poll: " + queue);
    }
}

Output:

PriorityQueue: [50, 40, 30, 10]
Polled Element: 50
PriorityQueue after poll: [40, 10, 30]

In this example, the PriorityQueue is ordered in descending order, and 50 (the largest element) is polled first.

Example 3: Using PriorityQueue with Custom Objects

You can also use a PriorityQueue to store objects, as long as the objects implement the Comparable interface or you provide a custom comparator.

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;
    }

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

public class Main {
    public static void main(String[] args) {
        // Creating a PriorityQueue of Task objects (based on priority)
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(Comparator.comparingInt(t -> t.priority));

        // Adding tasks to the queue
        taskQueue.offer(new Task("Task 1", 3));
        taskQueue.offer(new Task("Task 2", 1));
        taskQueue.offer(new Task("Task 3", 2));

        // Display the queue
        System.out.println("Task Queue: " + taskQueue);

        // Poll the highest priority task
        System.out.println("Polled Task: " + taskQueue.poll());

        // Display the queue after polling
        System.out.println("Task Queue after poll: " + taskQueue);
    }
}

Output:

Task Queue: [Task 2 (Priority: 1), Task 3 (Priority: 2), Task 1 (Priority: 3)]
Polled Task: Task 2 (Priority: 1)
Task Queue after poll: [Task 3 (Priority: 2), Task 1 (Priority: 3)]

In this case, the PriorityQueue uses the priority field of the Task objects to determine the order. The task with the highest priority (the lowest numeric value) is polled first.

When to Use a Java PriorityQueue

The PriorityQueue is suitable for use cases where elements need to be processed based on priority, such as:

• Task Scheduling: Managing tasks that need to be executed in priority order.
• Dijkstra's Algorithm: Used for finding the shortest path in graphs, where vertices are processed in order of distance (priority).
• Huffman Encoding: A key part of data compression algorithms, where symbols are processed in order of frequency.
• Event Simulation: Simulating events in order of their scheduled time or priority.

PriorityQueue vs. Other Data Structures

• PriorityQueue vs. LinkedList: A PriorityQueue automatically orders its elements based on priority, while a LinkedList stores elements in the order they are inserted.
• PriorityQueue vs. ArrayDeque: Both are queue implementations, but a PriorityQueue orders its elements by priority, while an ArrayDeque is a simple queue following FIFO order.
• PriorityQueue vs. TreeSet: A TreeSet stores elements in a sorted order based on their natural ordering or a comparator, but unlike a PriorityQueue, it does not allow duplicates.