PriorityQueue is a Queue data structure implementation in which objects are processed based on their priority. It’s part of the Java Collections Framework and is present in the java.util package.

Key Points:

Natural Ordering and Comparators: By default, elements are ordered in natural order (least to greatest). However, you can also specify a comparator to define custom ordering.

Null Values: PriorityQueue doesn’t allow null values.

Non-Thread Safe: Just like other collections, it’s not thread-safe. External synchronization must be provided if multiple threads modify it concurrently.

Capacity Growth: The queue grows automatically if it runs out of space.

Not Guarantee Specific Order: While elements are ordered based on their priority, it doesn’t guarantee any specific order for elements with equal priority.

Priority Queue Common Operations

import java.util.PriorityQueue;

public class PriorityQueueMethods {
    public static void main(String[] args) {
        // Create a priority queue of integers
        PriorityQueue<Integer> numbers = new PriorityQueue<>();

        // 1. Add numbers to the priority queue
        numbers.add(15);
        numbers.add(10);
        numbers.add(25);
        numbers.add(5);

        // 2. Peek (retrieve but not remove) the head of the queue
        System.out.println("Peek: " + numbers.peek());

        // 3. Poll (retrieve and remove) the head of the queue
        System.out.println("Poll: " + numbers.poll());

        // 4. Check if the queue contains a specific number
        System.out.println("Contains 15? " + numbers.contains(15));

        // 5. Remove a specific number
        numbers.remove(15);
        System.out.println("Contains 15 after removal? " + numbers.contains(15));

        // 6. Get the size of the queue
        System.out.println("Size: " + numbers.size());

        // 7. Clear the priority queue
        numbers.clear();
        System.out.println("Size after clear: " + numbers.size());
    }
}

Output:

Peek: 5
Poll: 5
Contains 15? true
Contains 15 after removal? false
Size: 2
Size after clear: 0

Explanation:

1. A PriorityQueue of integers is created and populated.

2. The peek method retrieves the head of the queue (smallest integer) without removing it.

3. The poll method retrieves and removes the head of the queue.

4. The contains method checks if the queue contains a specific number.

5. The remove method removes a specific number from the queue.

6. The size method returns the number of elements in the queue.

7. The clear method removes all elements from the queue.

Priority Queue of User-Defined Objects

import java.util.PriorityQueue;

class Person implements Comparable<Person> {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Person other) {
        return this.age - other.age; // Compare based on age
    }

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

public class PriorityQueueUserDefined {
    public static void main(String[] args) {
        // 1. Create a priority queue of Person objects
        PriorityQueue<Person> people = new PriorityQueue<>();

        // 2. Add person objects to the priority queue
        people.add(new Person("John", 35));
        people.add(new Person("Doe", 25));
        people.add(new Person("Jane", 30));

        // 3. Poll (retrieve and remove) person objects from the priority queue based on age
        while(!people.isEmpty()) {
            System.out.println("Polling: " + people.poll());
        }
    }
}

Output:

Polling: Doe: 25
Polling: Jane: 30
Polling: John: 35

Explanation:

1. A Person class is defined which implements Comparable interface to determine the order in the PriorityQueue.

2. The compareTo method is overridden to compare Person objects based on their age.

3. A PriorityQueue of Person objects is created and populated.

4. The poll method retrieves and removes the Person with the lowest age (highest priority) until the queue is empty.

Real-World Example: Employee Management based on Priority

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

class Employee {
    String name;
    int priority;

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

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

public class EmployeeManagement {
    public static void main(String[] args) {
        // Creating a priority queue with custom comparator to manage employees based on their priority
        PriorityQueue<Employee> queue = new PriorityQueue<>(Comparator.comparingInt(emp -> emp.priority));

        // Adding employees to the queue
        queue.add(new Employee("Alice", 3));
        queue.add(new Employee("Bob", 1));
        queue.add(new Employee("Charlie", 2));
        queue.add(new Employee("David", 4));

        // Displaying and processing employees based on priority
        while(!queue.isEmpty()) {
            System.out.println("Processing: " + queue.poll());
        }
    }
}

Output:

Processing: Bob (Priority: 1)
Processing: Charlie (Priority: 2)
Processing: Alice (Priority: 3)
Processing: David (Priority: 4)

Explanation:

1. An Employee class is created with attributes name and priority. The toString method is overridden to represent the employee in a readable format.

2. The main class, EmployeeManagement, creates a PriorityQueue to manage employees based on their priority.

3. Employees are added to the PriorityQueue. The custom comparator ensures that employees with a lower priority value are processed first.

4. The employees are polled (removed and returned) from the queue and displayed, in order of their priority.