What is a PriorityQueue?

A PriorityQueue is a data structure that implements a priority queue abstract data type. Unlike a regular queue, elements in a priority queue are associated with a "priority." Elements with higher priority are dequeued before elements with lower priority. In Java, the PriorityQueue class provides an efficient implementation of this data structure using a heap. By default, the PriorityQueue orders elements in ascending order (min-heap).

PriorityQueue Class in Java

The java.util.PriorityQueue class provides the following key features:

• It is based on the heap data structure (usually a binary heap).
• It does not allow null elements.
• It is not thread-safe. If concurrent access is needed, use java.util.concurrent.PriorityBlockingQueue.
• The head of the queue is the least element according to the specified ordering. If multiple elements are tied for least value, the head is one of those elements.
• The offer, poll, remove(), and add methods provide basic queue operations.

Using the Built-in PriorityQueue Class

Basic Operations

Here's how to create and use a basic PriorityQueue:

 import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // Create a PriorityQueue (min-heap by default)
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // Add elements
        pq.offer(10);
        pq.offer(2);
        pq.offer(8);
        pq.offer(1);
        pq.offer(5);

        System.out.println("PriorityQueue: " + pq); // Output will vary due to heap internal structure, but the smallest will be at the top

        // Get the head (smallest element) without removing
        System.out.println("Peek: " + pq.peek());  // Output: 1

        // Remove the head (smallest element)
        System.out.println("Poll: " + pq.poll());  // Output: 1

        System.out.println("PriorityQueue after poll: " + pq); // Output will vary

        // Check if the queue is empty
        System.out.println("Is empty: " + pq.isEmpty()); // Output: false

        // Get the size
        System.out.println("Size: " + pq.size());   // Output: 4
    }
} 

Customizing Priority using Comparators

To customize the priority (e.g., create a max-heap or order based on a different criteria), you can use a Comparator.

 import java.util.PriorityQueue;
import java.util.Comparator;

public class PriorityQueueComparatorExample {
    public static void main(String[] args) {
        // Create a PriorityQueue with a custom Comparator (max-heap)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

        maxHeap.offer(10);
        maxHeap.offer(2);
        maxHeap.offer(8);
        maxHeap.offer(1);
        maxHeap.offer(5);

        System.out.println("Max Heap PriorityQueue: " + maxHeap); // Output will vary, but the largest will be at the top
        System.out.println("Peek (Max): " + maxHeap.peek());   // Output: 10
        System.out.println("Poll (Max): " + maxHeap.poll());   // Output: 10
        System.out.println("Max Heap PriorityQueue after poll: " + maxHeap); // Output will vary


        // Custom Comparator for objects based on a specific attribute (example: sorting Person objects by age)
        class Person {
            String name;
            int age;

            public Person(String name, int age) {
                this.name = name;
                this.age = age;
            }

            @Override
            public String toString() {
                return name + "(" + age + ")";
            }
        }

        PriorityQueue<Person> peopleQueue = new PriorityQueue<>(Comparator.comparingInt(p -> p.age)); // Sort by age (ascending)

        peopleQueue.offer(new Person("Alice", 30));
        peopleQueue.offer(new Person("Bob", 25));
        peopleQueue.offer(new Person("Charlie", 35));

        System.out.println("People Queue (sorted by age): " + peopleQueue); // Output will vary, but Bob will be at the top
        System.out.println("Oldest Person: " + peopleQueue.poll());

    }
} 

PriorityQueue in Competitive Programming

PriorityQueue is incredibly useful in competitive programming for problems involving:

• Finding the Kth smallest/largest element: Efficiently keep track of the k smallest/largest elements seen so far.
• Dijkstra's Algorithm: Used for finding the shortest path in a graph.
• Heap Sort: Although not typically used directly, it's the underlying algorithm for PriorityQueue.
• Merging K sorted arrays: Efficiently merge k sorted arrays into a single sorted array.
• Scheduling problems: Optimal scheduling based on priority.

Example Problems and Solutions

Problem 1: Kth Largest Element in an Array

Given an array of integers nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

 // Input: nums = [3,2,1,5,6,4], k = 2
// Output: 5 

 import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // Min-heap to store k largest elements

        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // Remove the smallest element if the heap size exceeds k
            }
        }

        return minHeap.peek(); // The smallest element in the heap is the kth largest overall
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        int result = sol.findKthLargest(nums, k);
        System.out.println("Kth largest element: " + result); // Output: 5
    }
} 

Problem 2: Merge K Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

 // Input: lists = [[1,4,5],[1,3,4],[2,6]]
// Output: [1,1,2,3,4,4,5,6] 

 import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;


class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class SolutionMergeKLists {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>( (a,b) -> a.val - b.val);

        for (ListNode head : lists){
            if (head != null) {
                pq.add(head);
            }
        }


        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;

        while(!pq.isEmpty()){
            ListNode curr = pq.poll();
            tail.next = curr;
            tail = curr;

            if (curr.next != null){
                pq.add(curr.next);
            }
        }

        return dummy.next;

    }

    public static void main(String[] args) {
        SolutionMergeKLists sol = new SolutionMergeKLists();
        // Create some sample linked lists for testing
        ListNode list1 = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode list3 = new ListNode(2, new ListNode(6));

        ListNode[] lists = {list1, list2, list3};

        ListNode mergedList = sol.mergeKLists(lists);

        // Print the merged list (optional)
        ListNode current = mergedList;
        System.out.print("[");
        while (current != null) {
            System.out.print(current.val);
            if (current.next != null) {
                System.out.print(", ");
            }
            current = current.next;
        }
        System.out.println("]"); // Output: [1, 1, 2, 3, 4, 4, 5, 6]
    }
}