Topic 39 of 78
Priority Queue
Overview
A standard Queue is strictly 'First-In, First-Out'. But what if a VIP walks into the store? A Priority Queue completely ignores the order of arrival. Instead, every element is assigned a 'Priority', and the element with the highest priority is ALWAYS the one dequeued next. Under the hood, it is usually implemented using a specialized tree structure called a Heap.
Syntax
Adding (`offer`) and removing (`poll`) elements in a Priority Queue takes O(log N) time, which is incredibly fast for maintaining a constantly sorted stream of data.
Using Java's Built-in PriorityQueue
java
// By default, Java's PriorityQueue is a MIN-HEAP (smallest number comes out first)
Queue<Integer> pq = new PriorityQueue<>();
pq.offer(10);
pq.offer(5);
pq.offer(20);
// Even though 10 was added first, 5 has the highest priority (smallest)
System.out.println(pq.poll()); // Outputs 5
System.out.println(pq.poll()); // Outputs 10
// Creating a MAX-HEAP (largest number comes out first)
Queue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());
maxPq.offer(10);
maxPq.offer(5);
maxPq.offer(20);
System.out.println(maxPq.poll()); // Outputs 20!Common Pitfalls
- Assuming that iterating over a `PriorityQueue` using a for-each loop will print elements in sorted order. It won't! The internal tree array is not fully sorted. You MUST use `poll()` to get them in order.
- Adding custom objects without providing a Comparator, resulting in a ClassCastException.
Interview Tips
- Priority Queues ignore insertion order and always serve the highest priority element next. Under the hood, they use a Binary Heap.
Real-World Example
Emergency room triage systems, operating system task scheduling, and Dijkstra's Shortest Path algorithm all strictly rely on Priority Queues.
example
java
public class EmergencyRoom {
// Custom comparator: higher severity gets processed FIRST
Queue<Patient> triage = new PriorityQueue<>(
(p1, p2) -> Integer.compare(p2.severity, p1.severity)
);
public void admit(Patient p) { triage.offer(p); }
public void treatNext() {
Patient next = triage.poll();
System.out.println("Treating: " + next.name);
}
}