How to create PriorityQueue program in java

import java.util.*;

class PriorityQueue_TechSarvam 
{
    public static void main(String args[]) 
    {
        // Creating a PriorityQueue
        PriorityQueue<String> queue = new PriorityQueue<String>();
        
        // Adding elements to the PriorityQueue
        queue.add("Rajendra");
        queue.add("Mahendra");
        queue.add("Raja");
        queue.add("TechSarvam");
        queue.add("Rahul");

        // Displaying the head elements
        System.out.println("Head: " + queue.element());
        System.out.println("Head: " + queue.peek());

        // Iterating over the queue elements
        System.out.println("Iterating the queue elements:");
        Iterator<String> itr = queue.iterator();
        while (itr.hasNext()) 
        {
            System.out.println(itr.next());
        }

        // Removing two elements
        queue.remove();
        queue.poll();

        // Displaying queue after removal
        System.out.println("After removing two elements:");
        Iterator<String> itr2 = queue.iterator();
        while (itr2.hasNext()) 
        {
            System.out.println(itr2.next());
        }
    }
}

Step-by-Step Explanation:

1. Importing Required Classes:

 import java.util.*;

 This line imports necessary classes from the java.util package, including PriorityQueue and Iterator.

2. Class Declaration:

class PriorityQueue_TechSarvam {

A class PriorityQueue_TechSarvam is declared. This class defines the main() method from where the execution of the program begins.

3. Main Method:

public static void main(String args[]) {

The main() method is the entry point of the program. The program starts execution from there.

4. Creating a PriorityQueue:

PriorityQueue<String> queue = new PriorityQueue<String>();

Creates a PriorityQueue named queue, capable of storing elements of type String.

Important Point: A PriorityQueue is an unordered collection whose elements are ordered according to their natural ordering (in case of string: alphabetical ordering) or according to a comparator provided at the creation time of the PriorityQueue. Whenever elements are accessed, they appear in order of priority.

5. Adding Elements to the PriorityQueue:

queue.add(“Rajendra”);

queue.add(“Mahendra”);

queue.add(“Raja”);

queue.add(“TechSarvam”);

queue.add(“Rahul”);

•  The add() method is used to add elements to the PriorityQueue. The elements are  “Rajendra”,  “Mahendra”,  “Raja”,  “TechSarvam”, and  “Rahul”.
• Key Thing about PriorityQueue: The PriorityQueue does not keep track of the order in which elements are added. Instead, it sorts them in order according to their natural order (alphabetically for strings).

6. Accessing the Head of the Queue:

System.out.println(“head:” + queue.element());

System.out.println(“head:” + queue.peek());

• The element() and peek() methods are used to access the head of the PriorityQueue.
• element(): Returns the head of the queue but throws an exception (NoSuchElementException) if the queue is empty.
• peek(): Returns the head of the queue but returns null if the queue is empty.
• Both the functions will return the same element here, which would be the element of the highest priority that is the smallest alphabetically in the queue.
• Because PriorityQueue is naturally ordered, “Mahendra” would be at the head as being the smallest alphabetically.

  Output:

  head:Mahendra

  head:Mahendra

7. Iteration of Queue:

Iterator itr = queue.iterator();

while (itr.hasNext()) {

      System.out.println(itr.next());

  }

•  An Iterator is created to iterate over the elements of the PriorityQueue.

Important Note on Iteration of PriorityQueue: The iterator() method of PriorityQueue does not guarantee that elements will be returned in the order of priority. It is because the Iterator does not care about the priority ordering of the elements and may iterate over them in any order.

Example Output (iterating in any order):

iterating the queue elements:

Rajendra

Mahendra

Raja

Rahul

TechSarvam

8. Removing Elements from the PriorityQueue:

 queue.remove();

 queue.poll();

•  remove(): Removes the head of the PriorityQueue. The element removed is the one with the highest priority (alphabetically smallest).
• poll(): Removes and returns the head of the PriorityQueue. It is similar to remove(), but poll() will return null if the queue is empty.
• After calling remove() and poll(), the elements  “Mahendra” and  “Raja” will be removed from the queue (since  “Mahendra” is the head and  “Raja” is now the next smallest element).

9. Iterating After Removing Elements:

 Iterator<String> itr2 = queue.iterator();

  while (itr2.hasNext()) {

      System.out.println(itr2.next());

  }

After removing two elements from the queue, another iteration is done to print the remaining elements. As discussed earlier, the iterator does not guarantee order according to priority, it might print elements in an arbitrary order.

Expected Output After Removing Two Elements:

  after removing two elements:

  Rajendra

  Rahul

  TechSarvam

Summary of Output:

1. Head of the Queue (after peek() and element()):

  head:Mahendra

  head:Mahendra

2. Iterating the Queue (order not guaranteed):

iterating the queue elements:

Rajendra

Mahendra

Raja

Rahul

TechSarvam

3. After Removing Two Elements (remove() and poll()):

after removing two elements:

Rajendra

Rahul

TechSarvam

Key Points:

• PriorityQueue ensures elements are arranged in their natural ordering or using a custom comparator, not in the order elements are added to the queue.
• peek() and element() get a look at the head of the queue but peek() is safer, as it just returns null if it is an empty queue.
• The Iterator does not offer any guarantee as to order when iterating over elements in a PriorityQueue; it may or may not go in priority order.
• The following operations remove the head of a queue: remove() and poll(). However, poll() returns null for an empty queue. In contrast, remove() throws an exception if the queue is empty.

Time Complexity:

For each element:

• Add Operation (add(): O(log n).
• Remove Operation (remove() and poll(): O(log n) to get the element that has the highest priority.
• Iterator operation: O(n) to obtain all elements.