Java PriorityQueue

The PriorityQueue in Java is part of the Java Collections Framework and implements the Queue interface. It is used when you want elements to be processed based on their priority, not just in the order they were added.

By default, PriorityQueue in Java functions as a Min Heap, meaning the smallest element is always at the head of the queue. However, we can create a Max Heap by providing a custom comparator.

Key Characteristics#

• Implements Queue interface.
• Heap-based implementation.
• By default, it is a Min Heap (lowest value first).
• Null elements are not allowed.
• Not thread-safe.
• Accepts a custom Comparator to define ordering.

Constructors#

Commonly Used Methods (with Examples)#

1. offer(E e) - Adds an element to the queue#

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);
System.out.println("PriorityQueue: " + pq);

Output:

PriorityQueue: [10, 30, 20]

2. add(E e) - Same as offer, throws exception if unable to add#

pq.add(40);
System.out.println("After add: " + pq);

Output:

After add: [10, 30, 20, 40]

3. peek() - Retrieves head without removing#

System.out.println("Peek: " + pq.peek());

Output:

Peek: 10

4. element() - Similar to peek, but throws exception if empty#

System.out.println("Element: " + pq.element());

Output:

Element: 10

5. poll() - Retrieves and removes head, returns null if empty#

System.out.println("Polled: " + pq.poll());
System.out.println("After poll: " + pq);

Output:

Polled: 10
After poll: [20, 30, 40]

6. remove() - Retrieves and removes head, throws exception if empty#

System.out.println("Removed: " + pq.remove());
System.out.println("After remove: " + pq);

Output:

Removed: 20
After remove: [30, 40]

7. size() - Returns the size of the queue#

System.out.println("Size: " + pq.size());

Output:

Size: 2

8. contains(Object o) - Checks if element exists#

System.out.println("Contains 30? " + pq.contains(30));

Output:

Contains 30? true

9. toArray() - Converts queue to an array#

Object[] arr = pq.toArray();
System.out.println("Array: " + Arrays.toString(arr));

Output:

Array: [30, 40]

Max Heap using PriorityQueue#

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(10);
maxHeap.offer(30);
maxHeap.offer(20);
System.out.println("MaxHeap: " + maxHeap);

Output:

MaxHeap: [30, 10, 20]

PriorityQueue with Custom Comparator (String Length)#

PriorityQueue<String> stringQueue = new PriorityQueue<>(Comparator.comparingInt(String::length));
stringQueue.offer("Banana");
stringQueue.offer("Apple");
stringQueue.offer("Fig");

while (!stringQueue.isEmpty()) {
    System.out.println(stringQueue.poll());
}

Output:

Fig
Apple
Banana

Performance of PriorityQueue#

Explanation:

• Insertion and removal are O(log n) because they involve maintaining the heap property.
• peek() is O(1) because it just accesses the head.
• contains() and iteration are linear because the heap is not sorted.

Limitations of PriorityQueue#

• Cannot add null elements.
• No constant time retrieval of arbitrary elements.
• Iteration does not guarantee sorted order.
• Not synchronized (use PriorityBlockingQueue for thread-safe version).

Real-World Use Cases#

• Task Scheduling (OS-level job schedulers)
• Dijkstra’s Shortest Path Algorithm
• A* Search Algorithm
• Huffman Encoding Tree
• Event-driven Simulations

Conclusion#

The PriorityQueue is a powerful class when you need to process elements based on priority rather than insertion order. With support for custom comparators, it can adapt to many complex data-processing needs. Be cautious of its limitations in concurrency and ordering while iterating. In the next blog, we’ll explore ArrayDeque in detail, covering all methods and examples.