A PriorityQueue in Java is a special type of queue where elements are ordered based on their natural ordering or a custom comparator, not by the order in which they were added. The element with the highest priority is always at the front of the queue.

Key Characteristics

• Heap-Based: PriorityQueue is backed by a binary heap. This structure is what allows it to efficiently retrieve the highest-priority element.
• Not Thread-Safe: It’s not synchronized, so if you need a thread-safe version, consider using PriorityBlockingQueue.
• No Nulls: It does not allow null elements.
• Duplicates Allowed: It can contain duplicate elements.

Creating a PriorityQueue

You can instantiate a PriorityQueue in several ways.

1. Default Constructor

This creates a PriorityQueue with a default initial capacity (11) that orders elements according to their natural ordering (e.g., ascending for numbers, alphabetical for strings).

import java.util.PriorityQueue;

// For integers, smallest number has the highest priority
PriorityQueue<Integer> pq = new PriorityQueue<>();

// For strings, alphabetical order
PriorityQueue<String> stringPq = new PriorityQueue<>();

2. Specifying Initial Capacity

You can create a PriorityQueue with a specific initial capacity to avoid resizing overhead.

// Initial capacity of 20
PriorityQueue<Integer> pqWithCapacity = new PriorityQueue<>(20);

3. Using a Custom Comparator

This is the most powerful way to control the priority. You can define a custom Comparator to specify your own ordering logic. For example, to create a max-heap where the largest element has the highest priority.

import java.util.Collections;

// Max-heap for integers
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// Using a lambda expression for a custom comparator
PriorityQueue<Integer> customPq = new PriorityQueue<>((a, b) -> b - a); // a max-heap

You can also create a separate class that implements the Comparator interface for more complex logic.

import java.util.Comparator;

class LengthComparator implements Comparator<String> {
    @Override
    public int compare(String s1, String s2) {
        return s1.length() - s2.length();
    }
}

PriorityQueue<String> lengthPq = new PriorityQueue<>(new LengthComparator());

Note: The iterator() method does not guarantee a specific traversal order. It will not be ordered by priority. If you need ordered traversal, you must retrieve elements using poll().

Example: Min-Heap and Max-Heap

Let’s walk through a practical example of both a min-heap and a max-heap.

Min-Heap (Default Behavior)

import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        // Creates a min-heap (smallest number has highest priority)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // Add elements
        minHeap.add(30);
        minHeap.add(10);
        minHeap.add(50);
        minHeap.add(20);

        System.out.println("Min-heap elements: " + minHeap);
        // The output might be [10, 20, 50, 30] or similar. The internal representation is a heap, not a sorted array.
        // It's not guaranteed to be fully sorted in print.

        // Poll elements to see the order
        System.out.println("Polling elements from min-heap:");
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " "); // Prints: 10 20 30 50
        }
    }
}

Max-Heap (Using Collections.reverseOrder())

import java.util.Collections;
import java.util.PriorityQueue;

public class MaxHeapExample {
    public static void main(String[] args) {
        // Creates a max-heap (largest number has highest priority)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // Add elements
        maxHeap.add(30);
        maxHeap.add(10);
        maxHeap.add(50);
        maxHeap.add(20);

        System.out.println("Max-heap elements: " + maxHeap);
        // The output might be [50, 20, 30, 10] or similar. Again, internal heap structure is not fully sorted.

        // Poll elements to see the order
        System.out.println("Polling elements from max-heap:");
        while (!maxHeap.isEmpty()) {
            System.out.print(maxHeap.poll() + " "); // Prints: 50 30 20 10
        }
    }
}

PriorityQueue with Custom Objects

To use a PriorityQueue with a custom object, your class must either:

1. Implement the Comparable interface: This is for the natural ordering of your objects. The compareTo() method will define the priority.
2. Provide a Comparator: This is more flexible and is used when you want to define an ordering that is separate from the class’s natural ordering.

Internal Structure: Binary Heap

The internal data structure that powers PriorityQueue is a binary heap, which is a complete binary tree. This structure ensures that the element with the highest priority is always at the root. When you add or remove an element, the heap property (either min-heap or max-heap) is maintained by “bubbling up” or “bubbling down” the element, a process that takes O(logn) time. The root of the tree corresponds to the element that would be returned by peek() or poll().