PriorityQueue

TL;DR

• PriorityQueue is a Queue implementation that does not order elements strictly FIFO.
• Instead, elements are ordered according to their priority.
• The “highest priority” element is always at the head of the queue.
• Backed by a Min-Heap data structure.

Concept

When you use poll() on a PriorityQueue, you don’t get the oldest element; you get the smallest element (or largest, if you define the priority that way).

To determine priority, the elements must be comparable.

1. Natural Ordering: Elements must implement Comparable. By default, PriorityQueue acts as a Min-Heap, meaning the smallest item is at the head.
2. Custom Ordering: You can pass a custom Comparator to the constructor.

It provides $O(\log n)$ time for offer() and poll().

Examples

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        
        // 1. Natural Ordering (Min-Heap - smallest first)
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(50);
        pq.offer(10);
        pq.offer(30);
        
        System.out.println("Head: " + pq.peek()); // 10
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " "); // 10 30 50
        }
        System.out.println();
        
        // 2. Custom Ordering (Max-Heap - largest first)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        maxHeap.offer(50);
        maxHeap.offer(10);
        maxHeap.offer(30);
        
        System.out.println("Max Head: " + maxHeap.peek()); // 50
    }
}

Interview Questions

Q: If you print a PriorityQueue using System.out.println(), will it be sorted?
A: No. Printing a PriorityQueue iterates over its internal array representation of the Heap data structure. While the head (index 0) is guaranteed to be the highest priority item, the rest of the array is not fully sorted. The only way to retrieve the items in strict sorted order is to call poll() repeatedly.

Q: How are elements stored internally in a PriorityQueue?
A: Internally, it uses a balanced binary heap, represented by an array. For any node at index $i$, its children are located at indices $2i+1$ and $2i+2$. This allows it to efficiently maintain the heap property without the overhead of node pointers.