Java Course Navigation

What is PriorityQueue?

PriorityQueue is a special type of queue where elements are ordered based on their priority rather than insertion order. It's part of the java.util package and implements the Queue interface. Think of it like an emergency room - patients aren't treated in the order they arrive, but based on how critical their condition is!

Internally, PriorityQueue uses a heap data structure (min-heap by default) to maintain elements in priority order. This makes it perfect for scenarios like task scheduling, finding shortest paths, and managing events by priority.

Priority-Based: Elements are ordered by priority, not insertion order
Natural Ordering: Uses natural ordering for numbers and strings by default
Custom Ordering: Can define custom priority using Comparator
Heap Structure: Internally uses min-heap for efficient operations
No Null Elements: Does not allow null values
Not Thread-Safe: Use PriorityBlockingQueue for multi-threading

💡 Key Point: By default, PriorityQueue orders elements in ascending order (smallest/lowest first). For numbers, 1 comes before 10. For strings, "Apple" comes before "Banana".

Creating and Using PriorityQueue

Here's how to create a PriorityQueue with natural ordering:

Example: PriorityQueue Basic Operations

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // Creating a PriorityQueue (min-heap by default)
        PriorityQueue numbers = new PriorityQueue<>();
        
        // Adding elements in random order
        numbers.offer(30);
        numbers.offer(10);
        numbers.offer(50);
        numbers.offer(20);
        numbers.offer(40);
        
        System.out.println("PriorityQueue: " + numbers);
        
        // Peek - view highest priority element (smallest)
        System.out.println("Highest priority (smallest): " + numbers.peek());
        
        // Poll - remove elements in priority order
        System.out.println("\nRemoving elements in priority order:");
        while (!numbers.isEmpty()) {
            System.out.println("Removed: " + numbers.poll());
        }
        
        // Example with strings
        System.out.println("\n--- String PriorityQueue ---");
        PriorityQueue names = new PriorityQueue<>();
        
        names.offer("Zebra");
        names.offer("Apple");
        names.offer("Mango");
        names.offer("Banana");
        
        System.out.println("Names in priority order:");
        while (!names.isEmpty()) {
            System.out.println(names.poll());
        }
    }
}

Output:

PriorityQueue: [10, 20, 50, 30, 40]
Highest priority (smallest): 10

Removing elements in priority order:
Removed: 10
Removed: 20
Removed: 30
Removed: 40
Removed: 50

--- String PriorityQueue ---
Names in priority order:
Apple
Banana
Mango
Zebra

Explanation:

offer(element) - Adds element and maintains heap property
poll() - Removes and returns highest priority element (smallest by default)
peek() - Views highest priority element without removing
Elements are NOT stored in sorted order internally, but removed in priority order
For numbers: smaller values have higher priority (min-heap)
For strings: alphabetical order (A before Z)

Custom Priority with Comparator

You can define custom priority using a Comparator. Here's how to reverse the order or create complex priority rules:

Example: Custom Priority Order

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

public class CustomPriorityExample {
    public static void main(String[] args) {
        // Max-Heap: Largest number has highest priority
        System.out.println("=== Max-Heap (Largest First) ===");
        PriorityQueue maxHeap = 
            new PriorityQueue<>(Comparator.reverseOrder());
        
        maxHeap.offer(10);
        maxHeap.offer(50);
        maxHeap.offer(30);
        maxHeap.offer(20);
        
        System.out.println("Removing from max-heap:");
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll());
        }
        
        // Custom objects with priority
        System.out.println("\n=== Task Priority Queue ===");
        PriorityQueue taskQueue = new PriorityQueue<>();
        
        taskQueue.offer(new Task("Fix bug", 1));        // High priority
        taskQueue.offer(new Task("Write docs", 3));     // Low priority
        taskQueue.offer(new Task("Code review", 2));    // Medium priority
        taskQueue.offer(new Task("Critical bug", 1));   // High priority
        
        System.out.println("Processing tasks by priority:");
        while (!taskQueue.isEmpty()) {
            Task task = taskQueue.poll();
            System.out.println(task);
        }
    }
}

class Task implements Comparable {
    String name;
    int priority;  // 1 = High, 2 = Medium, 3 = Low
    
    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }
    
    @Override
    public int compareTo(Task other) {
        return this.priority - other.priority;  // Lower number = higher priority
    }
    
    @Override
    public String toString() {
        String level = priority == 1 ? "HIGH" : 
                      priority == 2 ? "MEDIUM" : "LOW";
        return "Task: " + name + " [Priority: " + level + "]";
    }
}

Output:

=== Max-Heap (Largest First) ===
Removing from max-heap:
50
30
20
10

=== Task Priority Queue ===
Processing tasks by priority:
Task: Fix bug [Priority: HIGH]
Task: Critical bug [Priority: HIGH]
Task: Code review [Priority: MEDIUM]
Task: Write docs [Priority: LOW]

Explanation:

Comparator.reverseOrder() - Creates a max-heap (largest first)
Custom objects must implement Comparable or provide a Comparator
compareTo() - Negative means higher priority, positive means lower
Tasks with priority 1 (HIGH) are processed before priority 3 (LOW)

PriorityQueue Methods

1. Adding Elements

Insert elements while maintaining heap property.

Methods: offer(element), add(element) - Both reorder elements by priority

2. Removing Elements

Remove the highest priority element from the queue.

Methods: poll() - Returns null if empty, remove() - Throws exception if empty

3. Examining Elements

View the highest priority element without removing it.

Methods: peek() - Returns null if empty, element() - Throws exception if empty

4. Utility Methods

Check queue status and work with multiple elements.

Methods: size(), isEmpty(), clear(), contains(element), toArray()

Practical Example: Hospital Emergency Room

Let's simulate an emergency room where patients are treated based on severity, not arrival time:

Example: ER Patient Management

import java.util.PriorityQueue;

public class EmergencyRoom {
    
    public static void main(String[] args) {
        PriorityQueue erQueue = new PriorityQueue<>();
        
        System.out.println("=== Emergency Room Queue ===\n");
        
        // Patients arrive in this order
        System.out.println("Patients arriving:");
        admitPatient(erQueue, new Patient("John", 3));      // Minor injury
        admitPatient(erQueue, new Patient("Sarah", 1));     // Critical
        admitPatient(erQueue, new Patient("Mike", 2));      // Serious
        admitPatient(erQueue, new Patient("Emma", 1));      // Critical
        admitPatient(erQueue, new Patient("Tom", 4));       // Very minor
        
        System.out.println("\nTotal patients waiting: " + erQueue.size());
        
        // Treat patients by priority
        System.out.println("\n--- Treating Patients by Severity ---");
        int doctorNumber = 1;
        
        while (!erQueue.isEmpty()) {
            Patient patient = erQueue.poll();
            System.out.println("Doctor " + doctorNumber + ": Treating " + 
                             patient);
            doctorNumber++;
        }
        
        System.out.println("\n✓ All patients treated!");
    }
    
    static void admitPatient(PriorityQueue queue, Patient patient) {
        queue.offer(patient);
        System.out.println("  Admitted: " + patient);
    }
}

class Patient implements Comparable {
    String name;
    int severity;  // 1=Critical, 2=Serious, 3=Minor, 4=Very minor
    
    public Patient(String name, int severity) {
        this.name = name;
        this.severity = severity;
    }
    
    @Override
    public int compareTo(Patient other) {
        return this.severity - other.severity;  // Lower = more critical
    }
    
    @Override
    public String toString() {
        String level = severity == 1 ? "CRITICAL" :
                      severity == 2 ? "SERIOUS" :
                      severity == 3 ? "MINOR" : "VERY MINOR";
        return name + " [" + level + "]";
    }
}

Output:

=== Emergency Room Queue ===

Patients arriving:
  Admitted: John [MINOR]
  Admitted: Sarah [CRITICAL]
  Admitted: Mike [SERIOUS]
  Admitted: Emma [CRITICAL]
  Admitted: Tom [VERY MINOR]

Total patients waiting: 5

--- Treating Patients by Severity ---
Doctor 1: Treating Sarah [CRITICAL]
Doctor 2: Treating Emma [CRITICAL]
Doctor 3: Treating Mike [SERIOUS]
Doctor 4: Treating John [MINOR]
Doctor 5: Treating Tom [VERY MINOR]

✓ All patients treated!

Explanation:

Patients are treated based on severity, not arrival order
Critical patients (severity 1) are treated before minor cases (severity 3-4)
Sarah arrives second but is treated first due to critical condition
Perfect for any priority-based scheduling system

Finding Top K Elements

PriorityQueue is excellent for finding the largest or smallest K elements efficiently:

Example: Top 3 Scores

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

public class TopKElements {
    public static void main(String[] args) {
        int[] scores = {78, 92, 85, 67, 95, 88, 73, 98, 81, 90};
        int k = 3;
        
        System.out.println("All scores: ");
        for (int score : scores) {
            System.out.print(score + " ");
        }
        
        // Find top 3 highest scores using max-heap
        PriorityQueue topScores = 
            new PriorityQueue<>(Comparator.reverseOrder());
        
        for (int score : scores) {
            topScores.offer(score);
        }
        
        System.out.println("\n\nTop " + k + " Highest Scores:");
        for (int i = 0; i < k && !topScores.isEmpty(); i++) {
            System.out.println((i + 1) + ". " + topScores.poll());
        }
        
        // Find 3 lowest scores using min-heap
        PriorityQueue lowScores = new PriorityQueue<>();
        
        for (int score : scores) {
            lowScores.offer(score);
        }
        
        System.out.println("\nBottom " + k + " Lowest Scores:");
        for (int i = 0; i < k && !lowScores.isEmpty(); i++) {
            System.out.println((i + 1) + ". " + lowScores.poll());
        }
    }
}

Output:

All scores: 
78 92 85 67 95 88 73 98 81 90 

Top 3 Highest Scores:
1. 98
2. 95
3. 92

Bottom 3 Lowest Scores:
1. 67
2. 73
3. 78

Explanation:

Max-heap (reverseOrder) gives largest elements first
Min-heap (natural order) gives smallest elements first
Efficient for finding top/bottom K elements from large datasets
Used in algorithms like finding median, ranking systems, and recommendations

PriorityQueue vs Other Collections

Understanding when to use PriorityQueue compared to other collections:

Comparison Table

Feature              PriorityQueue         Queue (LinkedList)  TreeSet
─────────────────────────────────────────────────────────────────────────────
Ordering             By priority           FIFO order            Sorted order
Duplicates           Allowed               Allowed               Not allowed
Access               Highest priority      Front only            No direct access
Structure            Heap (binary tree)    Linked nodes          Red-Black tree
Performance          O(log n) add/remove   O(1) add/remove       O(log n) operations
Use case             Priority scheduling   Sequential tasks      Unique sorted items

🎯 When to Use PriorityQueue: Choose PriorityQueue when you need to process elements by priority: task scheduling, event simulation, finding top K elements, Dijkstra's algorithm, Huffman coding, or any scenario where order matters but not insertion order.

Important Points to Remember

Keep these key characteristics in mind when working with PriorityQueue:

No Null Values: PriorityQueue does not accept null elements
Not Sorted Display: Internal array may not appear sorted when printed
Heap Property: Only the top element is guaranteed to be highest priority
Natural Ordering: Elements must be comparable or provide a Comparator
Efficient Operations: O(log n) for add/remove, O(1) for peek

⚠️ Common Mistake: Don't expect PriorityQueue to maintain complete sorted order throughout. It only guarantees that poll() returns the highest priority element. The internal structure is a heap, not a sorted array!

Java PriorityQueue

What is PriorityQueue?

Creating and Using PriorityQueue

Example: PriorityQueue Basic Operations

Custom Priority with Comparator

Example: Custom Priority Order

PriorityQueue Methods

1. Adding Elements

2. Removing Elements

3. Examining Elements

4. Utility Methods

Practical Example: Hospital Emergency Room

Example: ER Patient Management

Finding Top K Elements

Example: Top 3 Scores

PriorityQueue vs Other Collections

Comparison Table

Important Points to Remember