What is a Priority Queue?

A Priority Queue is a specialized data structure that retains elements in a way that prioritizes certain elements over others. Unlike standard queues that follow a first-in, first-out (FIFO) principle, priority queues allow for retrieval that is based on the priority of the elements.

In typical implementations, each element has a priority associated with it, and elements with higher priorities are dequeued before those with lower priorities. If two elements have the same priority, they are processed according to their order in the queue.

Use Cases of Priority Queues

Priority queues have a wide range of applications, including:

• Job scheduling in operating systems
• Implementing algorithms like Dijkstra's and Prim's
• Managing events in a simulation
• A* search algorithm in games and pathfinding

Implementing Priority Queue in Java

Java provides a built-in implementation of a priority queue through the PriorityQueue class in the java.util package. Below are the basic steps to implement and work with PriorityQueue.

Step 1: Import the Necessary Package

To use PriorityQueue, start by importing the package:

import java.util.PriorityQueue;

Step 2: Create a Priority Queue

You can create a simple priority queue using the default natural ordering of its elements or by providing a custom comparator.

Example: Default Ordering

Here's how you can create a priority queue with default natural ordering using integers:

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(5);
pq.add(20);
pq.add(15);

// The element with the highest priority (smallest integer) will be at the head of the queue
System.out.println("Priority Queue: " + pq);

Output:

Priority Queue: [5, 10, 20, 15]

In this example, the integer with the smallest value has the highest priority.

Step 3: Retrieve the Head of the Queue

To retrieve and remove the head of the queue (the highest priority element), use the poll() method:

int head = pq.poll();
System.out.println("Head of queue: " + head);
System.out.println("Updated Priority Queue: " + pq);

Output:

Head of queue: 5
Updated Priority Queue: [10, 15, 20]

Custom Priority Queue with Comparator

Sometimes, you might need elements ordered based on custom criteria. This can be achieved using a Comparator. Below is an example of setting up a priority queue that prioritizes strings by their length:

PriorityQueue<String> stringPQ = new PriorityQueue<>((s1, s2) -> Integer.compare(s1.length(), s2.length()));

// Adding elements
stringPQ.add("apple");
stringPQ.add("pear");
stringPQ.add("banana");
stringPQ.add("kiwi");

// Retrieving elements based on length
while (!stringPQ.isEmpty()) {
    System.out.println(stringPQ.poll());
}

Output:

kiwi
pear
apple
banana

In this example, strings are dequeued based on their length, demonstrating a custom ordering mechanism.

Additional Features of Priority Queue

The PriorityQueue class offers various methods that help in managing your queue:

1. peek(): Retrieves the head of the queue without removing it.
2. isEmpty(): Checks if the queue is empty.
3. size(): Returns the number of elements in the queue.

Example:

System.out.println("Is the queue empty? " + pq.isEmpty());
System.out.println("Size of the queue: " + pq.size());

Performance Analysis

The PriorityQueue in Java is backed by a binary heap, which provides efficient methods for inserting and removing elements:

• Time Complexity:
  • Insertion: O(log n)
  • Deletion: O(log n)
  • Searching: O(n)

This makes it quite suitable for scenarios where you need to perform a lot of insertions and deletions while maintaining the order of processing.

Real-World Application Example: Job Scheduling

Imagine a scenario where you need to manage job priorities in an operating system. Here's a skeleton implementation that uses PriorityQueue:

class Job implements Comparable<Job> {
    int id;
    int priority;

    Job(int id, int priority) {
        this.id = id;
        this.priority = priority;
    }

    @Override
    public int compareTo(Job other) {
        // Higher priority first
        return Integer.compare(other.priority, this.priority);
    }
}

public class JobScheduler {
    public static void main(String[] args) {
        PriorityQueue<Job> jobQueue = new PriorityQueue<>();

        jobQueue.add(new Job(1, 3));
        jobQueue.add(new Job(2, 1));
        jobQueue.add(new Job(3, 2));

        while (!jobQueue.isEmpty()) {
            Job job = jobQueue.poll();
            System.out.println("Processing job ID: " + job.id + " with priority: " + job.priority);
        }
    }
}

Output:

Processing job ID: 1 with priority: 3
Processing job ID: 3 with priority: 2
Processing job ID: 2 with priority: 1

This simulation shows how job IDs are processed based on priority, demonstrating the practical application of a priority queue in a scheduling system.