Priority Queue Implementation in Java

1. Introduction

A priority queue is a specialized queue data structure where each element has a priority. Elements are served based on their priority, not based on their order in the queue. The element with the highest priority is served before elements with lower priorities. In cases where two elements have the same priority, they are served based on their order in the queue. 

Priority queues are commonly used in algorithms like Dijkstra's shortest path, for task scheduling, and more.

2. Implementation Steps

1. Define a PriorityQueue class.

2. Within the class:

a. Declare an ArrayList to store the queue elements and their priorities.

b. Provide methods like insert(), delete(), peek(), and isEmpty().

3. Implement the methods with respect to the priority of the elements.

4. Create an instance of the priority queue class and perform operations to demonstrate its functionality.

3. Implementation in Java

import java.util.ArrayList;
import java.util.Comparator;
public class PriorityQueue<T> {
    private ArrayList<Element> queue;
    // Element inner class to store data and its priority
    private class Element {
        T data;
        int priority;
        Element(T data, int priority) {
            this.data = data;
            this.priority = priority;
        }
    }
    // Constructor
    public PriorityQueue() {
        queue = new ArrayList<>();
    }
    // Check if the queue is empty
    public boolean isEmpty() {
        return queue.isEmpty();
    }
    // Add element to the priority queue
    public void insert(T data, int priority) {
        Element newElement = new Element(data, priority);
        queue.add(newElement);
        queue.sort(Comparator.comparingInt(e -> -e.priority));  // Sort in descending order of priority
    }
    // Remove and return highest priority element from the queue
    public T delete() {
        if (isEmpty()) {
            System.out.println("PriorityQueue is empty. Can't delete.");
            return null;
        }
        return queue.remove(0).data;
    }
    // View highest priority element without removing it
    public T peek() {
        if (isEmpty()) {
            System.out.println("PriorityQueue is empty. Nothing to peek.");
            return null;
        }
        return queue.get(0).data;
    }
    public static void main(String[] args) {
        PriorityQueue<String> pq = new PriorityQueue<>();
        pq.insert("Task1", 2);
        pq.insert("Task2", 1);
        pq.insert("Task3", 3);
        System.out.println("Highest priority element: " + pq.peek());  // Outputs Task3
        System.out.println("Deleted element: " + pq.delete());  // Outputs Task3
        System.out.println("Highest priority element after delete: " + pq.peek());  // Outputs Task1
    }
}

Output:

Highest priority element: Task3
Deleted element: Task3
Highest priority element after delete: Task1

Explanation:

1. A generic PriorityQueue class is defined. This allows us to use the priority queue with any data type.

2. An inner class Element is created to store the data and its associated priority.

3. The isEmpty() method checks whether the priority queue is empty by checking the queue list.

4. The insert() method adds an element and its priority to the queue. After insertion, it sorts the queue in descending order of priority.

5. The delete() method removes and returns the highest priority element from the priority queue.

6. The peek() method returns the highest priority element without removing it.

7. In the main() method, we create a PriorityQueue of Strings, insert three tasks with different priorities, and perform some operations to demonstrate its functionality.