Topic 41 of 79

Priority Queue

Q: What is the time complexity of `offer()` and `poll()` in a Priority Queue?

Both `offer()` (insertion) and `poll()` (removal) run in O(log N) time. This is because adding or removing requires 'bubbling up' or 'sifting down' the tree to restore the heap property. Finding the minimum (`peek()`) is O(1).

Overview

A standard Queue follows strict FIFO: first in, first out. But what if you are in an emergency room? A patient with a paper cut who arrived first should NOT be treated before a patient with a heart attack who arrived second. This is where a Priority Queue is used.

A Priority Queue acts like a regular queue, but every element has a 'priority' associated with it. When you call poll(), it does not return the oldest element; it returns the element with the highest priority (or lowest priority, depending on configuration).

Under the hood, Java's PriorityQueue does NOT sort an array. It uses a Binary Min-Heap data structure. This allows it to find the minimum/maximum element in O(1) time, and insert or delete elements in O(log N) time. It is significantly faster than inserting into an array and sorting it (O(N log N)).

Syntax

Using Java's PriorityQueue

java

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

public class Main {
    public static void main(String[] args) {
        // 1. Default Min-Heap (Smallest numbers come out first)
        PriorityQueue<Integer> minPQ = new PriorityQueue<>();
        minPQ.offer(50);
        minPQ.offer(10);
        minPQ.offer(30);
        
        System.out.println(minPQ.poll()); // 10 (Smallest first!)
        
        // 2. Max-Heap (Largest numbers come out first)
        // We pass a Comparator to reverse the natural order
        PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
        maxPQ.offer(50);
        maxPQ.offer(10);
        maxPQ.offer(30);
        
        System.out.println(maxPQ.poll()); // 50 (Largest first!)
        
        // 3. Custom Objects (Requires Comparable or Comparator)
        PriorityQueue<Patient> erQueue = new PriorityQueue<>((p1, p2) -> 
            Integer.compare(p2.severity, p1.severity) // Higher severity first
        );
        erQueue.offer(new Patient("Alice", 2)); // Paper cut
        erQueue.offer(new Patient("Bob", 10));  // Heart attack
        
        System.out.println(erQueue.poll().name); // Bob is treated first
    }
}

Common Pitfalls

Assuming iteration order is sorted. If you do for (int x : pq) { System.out.println(x); }, the output will NOT be perfectly sorted! A heap only guarantees that the root is the minimum. To get sorted output, you must poll() in a while loop until empty.
Forgetting to provide a Comparator for custom objects. If you create a PriorityQueue<Student> and Student does not implement the Comparable interface, the moment you offer() the second student, Java will crash with a ClassCastException because it doesn't know how to compare them.
Using remove(Object) instead of poll(). While poll() removes the root in O(log N) time, searching for a specific object in the middle of a heap and removing it is an O(N) operation because heaps are not built for random searching.

Interview Questions

What is the time complexity of offer() and poll() in a Priority Queue?

Both offer() (insertion) and poll() (removal) run in O(log N) time. This is because adding or removing requires 'bubbling up' or 'sifting down' the tree to restore the heap property. Finding the minimum (peek()) is O(1).

How would you find the Kth largest element in an array of N elements?

Using a Min-Heap Priority Queue of size K. Iterate through the array, adding elements to the PQ. If the PQ size exceeds K, poll() the smallest element out. At the end of the array, the PQ holds the K largest elements, and the root (peek()) is exactly the Kth largest. This takes O(N log K) time, which is much faster than sorting the whole array O(N log N).

Real-World Example

Dijkstra's Algorithm for GPS navigation uses a Priority Queue. When exploring routes to a destination, the algorithm always wants to explore the 'currently known shortest path' next. A Priority Queue instantly provides the node with the lowest travel cost at every step.

example

java

PriorityQueue<RouteNode> pq = new PriorityQueue<>(
    (a, b) -> Integer.compare(a.costFromStart, b.costFromStart)
);

// Add the starting city
pq.offer(new RouteNode("New York", 0));

while (!pq.isEmpty()) {
    // O(1) to find, O(log N) to extract the cheapest path so far
    RouteNode cheapest = pq.poll(); 
    
    if (cheapest.city.equals(destination)) {
        return cheapest.costFromStart; // Found the shortest route!
    }
    
    // Explore neighbors...
}

Check Your Knowledge

Test your understanding of Priority Queue with these quick questions.

By default, what type of element does Java's PriorityQueue return first?

What is the time complexity of removing the highest priority element (`poll()`)?

If you iterate over a PriorityQueue using a for-each loop, what order will the elements be in?

Take Java Quiz

Overview

Syntax

Using Java's PriorityQueue

java

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

public class Main {
    public static void main(String[] args) {
        // 1. Default Min-Heap (Smallest numbers come out first)
        PriorityQueue<Integer> minPQ = new PriorityQueue<>();
        minPQ.offer(50);
        minPQ.offer(10);
        minPQ.offer(30);
        
        System.out.println(minPQ.poll()); // 10 (Smallest first!)
        
        // 2. Max-Heap (Largest numbers come out first)
        // We pass a Comparator to reverse the natural order
        PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
        maxPQ.offer(50);
        maxPQ.offer(10);
        maxPQ.offer(30);
        
        System.out.println(maxPQ.poll()); // 50 (Largest first!)
        
        // 3. Custom Objects (Requires Comparable or Comparator)
        PriorityQueue<Patient> erQueue = new PriorityQueue<>((p1, p2) -> 
            Integer.compare(p2.severity, p1.severity) // Higher severity first
        );
        erQueue.offer(new Patient("Alice", 2)); // Paper cut
        erQueue.offer(new Patient("Bob", 10));  // Heart attack
        
        System.out.println(erQueue.poll().name); // Bob is treated first
    }
}

Common Pitfalls

Assuming iteration order is sorted. If you do for (int x : pq) { System.out.println(x); }, the output will NOT be perfectly sorted! A heap only guarantees that the root is the minimum. To get sorted output, you must poll() in a while loop until empty.
Forgetting to provide a Comparator for custom objects. If you create a PriorityQueue<Student> and Student does not implement the Comparable interface, the moment you offer() the second student, Java will crash with a ClassCastException because it doesn't know how to compare them.
Using remove(Object) instead of poll(). While poll() removes the root in O(log N) time, searching for a specific object in the middle of a heap and removing it is an O(N) operation because heaps are not built for random searching.

Interview Questions

What is the time complexity of offer() and poll() in a Priority Queue?

How would you find the Kth largest element in an array of N elements?

Real-World Example

example

java

PriorityQueue<RouteNode> pq = new PriorityQueue<>(
    (a, b) -> Integer.compare(a.costFromStart, b.costFromStart)
);

// Add the starting city
pq.offer(new RouteNode("New York", 0));

while (!pq.isEmpty()) {
    // O(1) to find, O(log N) to extract the cheapest path so far
    RouteNode cheapest = pq.poll(); 
    
    if (cheapest.city.equals(destination)) {
        return cheapest.costFromStart; // Found the shortest route!
    }
    
    // Explore neighbors...
}

Check Your Knowledge

Test your understanding of Priority Queue with these quick questions.