PriorityQueue

About

A PriorityQueue is a queue in which each element is associated with a priority. The elements are ordered based on their priority, and elements with higher priority are dequeued before elements with lower priority. It is part of the java.utilpackage and implements the Queue interface.

Unlike a regular queue, which operates in a FIFO (First In, First Out) order, the PriorityQueue provides an ordering of elements according to their priority, where the element with the highest priority is dequeued first. By default, it orders elements according to their natural ordering (via Comparable), but a custom comparator can also be provided for custom ordering.

Elements of a priority queue may not be sorted. However, elements are always retrieved in sorted order.

Features

1. Unbounded: PriorityQueue is typically unbounded, meaning it can grow dynamically as elements are added.

2. Element Ordering: By default, elements are ordered in natural ascending order. However, a custom comparator can be provided for custom ordering.

3. Not Thread-Safe: PriorityQueue is not thread-safe. If multiple threads will access the queue concurrently, external synchronization or using PriorityBlockingQueue is needed.

4. No Null Elements: Null elements are not allowed in PriorityQueue. Attempting to insert a null will throw a NullPointerException.

5. Heap-Based Implementation: Internally, PriorityQueue uses a heap (usually a binary heap) to maintain the ordering of elements.

6. Custom Comparators: A custom comparator can be provided to define the priority ordering. This is useful for priority queues that are not based on natural ordering.

7. Efficient Insertions and Removals: Insertion (add()) and removal (poll()) operations are efficient, with a time complexity of O(log n).

8. Peeking at Head: The peek() operation allows you to view the element with the highest priority without removing it from the queue.

9. Support for Duplicates: The PriorityQueue allows duplicates, unlike some other collections that may reject duplicates.

Key Methods

Method Type	Method	Description
Add Operations	add(E e)	Inserts the specified element into the priority queue.
	offer(E e)	Inserts the specified element into the queue, returns false if full (rare).
Remove Operations	remove()	Removes a single instance of the specified element from the queue. This method differs from poll() only in that it throws an NoSuchElementException exception if this queue is empty.
	poll()	Retrieves and removes the highest priority element from the queue. Or returns null if this queue is empty.
Access Operations	peek()	Retrieves the highest priority element without removing it.
	element()	Retrieves the highest priority element without removing it. Throws exception if empty.
Size and Clearing	size()	Returns the number of elements in the priority queue.
	clear()	Removes all elements from the priority queue.
Iterators	iterator()	Returns an iterator over the elements of the priority queue.

Big O Time Complexity for PriorityQueue Operations

Operation	Time Complexity	Details
Insert (add/offer)	O(log n)	Insertion in the heap structure.
Remove (poll/remove)	O(log n)	Removal of the root element (highest priority).
Peek (peek/element)	O(1)	Accessing the root element without removal.
Search (contains)	O(n)	Searching for an element requires scanning through the queue.
Size	O(1)	Retrieving the number of elements in the queue.
Iterator	O(n)	Iterating over all elements in the queue.

Example

Basic Operation

import java.util.*;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // PriorityQueue with natural ordering
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // Add elements to the PriorityQueue
        pq.add(10);
        pq.add(20);
        pq.add(15);
        pq.add(5);

        // Display the PriorityQueue
        System.out.println("PriorityQueue: " + pq); //PriorityQueue: [5, 10, 15, 20]

        // Retrieve the highest priority element without removing
        System.out.println("Peek (highest priority): " + pq.peek()); //Peek (highest priority): 5

        // Retrieve and remove the highest priority element
        System.out.println("Polled (removed): " + pq.poll()); //Polled (removed): 5

        // Display the PriorityQueue after polling
        System.out.println("PriorityQueue after poll: " + pq); //PriorityQueue after poll: [10, 20, 15]

        // Iterate through the PriorityQueue
        System.out.println("Iterating through PriorityQueue:"); //Iterating through PriorityQueue:
        for (Integer element : pq) {
            System.out.println(element);
        }
        //10
        //20
        //15

        // Custom comparator to create a max-heap
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(10);
        maxHeap.add(20);
        maxHeap.add(15);
        maxHeap.add(5);

        // Display the max-heap
        System.out.println("Max-Heap: " + maxHeap); //Max-Heap: [20, 10, 15, 5]

        // Custom object example with priority
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority));
        taskQueue.add(new Task("Task 1", 2));
        taskQueue.add(new Task("Task 2", 1));
        taskQueue.add(new Task("Task 3", 3));

        System.out.println("Task Queue (ordered by priority): "); //Task Queue (ordered by priority): 
        while (!taskQueue.isEmpty()) {
            System.out.println(taskQueue.poll().getName());
        }
        //Task 2    
        //Task 1
        //Task 3
    }
}

class Task {
    private String name;
    private int priority;

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

    public String getName() {
        return name;
    }

    public int getPriority() {
        return priority;
    }
}

public class PriorityQueueExample {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        PriorityQueue<Integer> queue = new PriorityQueue<>(new ReverseOrderComparator());

        for (int i = 0; i < q; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();

            if (x == 1) {
                queue.add(y);
            } else if (x == 2) {
                if (queue.isEmpty()) {
                    System.out.println(-1);
                } else {
                    System.out.println(queue.peek());
                }
            } else if (x == 3) {
                queue.poll();
            }

        }
    }

    static class ReverseOrderComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1); // Reverse order
        }
    }
}

Using PriorityQueue for Task Scheduling (Max-Heap)

import java.util.*;

public class TaskScheduler {
    public static void main(String[] args) {
        // Max-heap using custom comparator
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority).reversed());

        // Adding tasks with different priorities
        taskQueue.add(new Task("Critical Task", 1));
        taskQueue.add(new Task("High Priority Task", 2));
        taskQueue.add(new Task("Low Priority Task", 5));

        // Scheduling tasks (polling from the queue)
        while (!taskQueue.isEmpty()) {
            Task task = taskQueue.poll();
            System.out.println("Executing: " + task.getName());
        }
    }
}

class Task {
    private String name;
    private int priority;

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

    public String getName() {
        return name;
    }

    public int getPriority() {
        return priority;
    }
}

PriorityQueue for Sorting Elements

import java.util.*;

public class SortWithPriorityQueue {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(15, 10, 20, 5, 30);
        PriorityQueue<Integer> pq = new PriorityQueue<>(numbers);

        System.out.println("Sorted elements using PriorityQueue:");
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");
        }
    }
}

When to Use PriorityQueue ?

1. Task Scheduling: Use PriorityQueue to schedule tasks where the priority of each task varies.

2. Dijkstra’s Algorithm: Priority queues are commonly used in graph algorithms like Dijkstra’s shortest path algorithm.

3. Real-time Systems: When processing events with different priorities (e.g., priority messaging systems).

4. Merging Multiple Sorted Streams: Use PriorityQueue to merge multiple sorted streams efficiently.