The PriorityQueue class is a part of the Java Collections Framework and provides a way to manage elements based on their priority rather than their insertion order. Unlike a standard FIFO queue, a PriorityQueue orders its elements either according to their natural ordering (if they implement Comparable) or according to a custom Comparator provided at queue construction time. This makes PriorityQueue ideal for applications like task scheduling, where tasks with higher priority should be processed before those with lower priority.

PriorityQueue is not synchronized, which means it is not thread-safe by default. For concurrent use, you must handle synchronization externally or use concurrent alternatives.

Hierarchy of PriorityQueue

The PriorityQueue class is a member of the Java Collections Framework and fits into the collection hierarchy as follows:

• Collection Interface
  The root interface for most collection classes.

  • Queue Interface
    A subinterface of Collection, which defines additional queue-specific operations.

    • PriorityQueue Class
      A concrete class that implements the Queue interface and orders its elements based on priority.

PriorityQueue also implements the Serializable interface, meaning that its state can be saved and restored. It does not implement the Deque interface; if you need a double-ended queue, consider using ArrayDeque instead.

Syntax for Creating a PriorityQueue

Basic Syntax:

PriorityQueue<Type> priorityQueue = new PriorityQueue<Type>();

• Explanation:
  • PriorityQueue<Type> declares a priority queue that will store objects of the specified Type.
  • The default constructor creates an empty priority queue that orders its elements according to their natural order.

Syntax with a Custom Comparator:

PriorityQueue<Type> priorityQueue = new PriorityQueue<Type>(customComparator);

• Explanation:
  • customComparator is an instance of a class that implements the Comparator<Type> interface.
  • This allows you to define a custom order for the elements.

Examples

Example 1: Basic Usage of PriorityQueue (Natural Order)

In this example, we create a PriorityQueue of integers. The elements are automatically arranged in their natural ascending order. We add several numbers to the queue, then use basic operations to demonstrate its behavior.

Example Explanation:

• Queue Creation:
  • A PriorityQueue of integers is created which will sort elements in natural (ascending) order.
• Adding Elements:
  • Elements 20, 5, 15, and 10 are added.
• Automatic Ordering:
  • The PriorityQueue organizes these elements such that the smallest element is at the head.
• Removing Elements:
  • The poll() method removes and returns the head element (the smallest number).
• Outcome:
  • The output displays the queue in natural order before and after removal.

Example 2: PriorityQueue with Custom Comparator (Descending Order)

This example demonstrates how to create a PriorityQueue with a custom comparator that sorts integers in descending order. The comparator is defined using an anonymous inner class.

Example Explanation:

• Custom Comparator:
  • A custom comparator is defined to sort integers in descending order by returning b - a in the compare() method.
• Queue Creation with Comparator:
  • A PriorityQueue is created with the custom comparator, ensuring that higher numbers have priority.
• Adding Elements:
  • Integers 20, 5, 15, and 10 are added to the queue.
• Ordering and Removal:
  • The queue arranges elements in descending order, and the poll() method removes the highest element first.
• Outcome:
  • The output demonstrates the custom ordering, with the highest number at the head of the queue before and after removal.

The PriorityQueue class in Java is a flexible data structure that orders elements based on priority rather than insertion order. Understanding PriorityQueue and custom comparators is essential for efficiently managing tasks, scheduling, and other operations where prioritization is key.