Internal Working of PriorityQueue in Java

Posted on: February 8, 2025 Posted by: rahulgite Comments: 0

Introduction

A PriorityQueue in Java is a part of the java.util package and is used to store elements in a priority-based order. Unlike a normal queue (FIFO), PriorityQueue orders its elements based on natural ordering (for Comparable objects) or custom order defined by a Comparator.

1. Data Structure Used

PriorityQueue is implemented using a binary heap, which ensures efficient retrieval of the highest or lowest priority element.

Implementation in Java:

public class PriorityQueue<E> extends AbstractQueue<E> {
    private transient Object[] queue;
    private int size;
}

The queue is an array-based binary heap.
The smallest (or highest priority) element is stored at the root (queue[0]).
The heap maintains the heap property using a binary tree structure.

Internally, PriorityQueue is a Min Heap by default, meaning the smallest element is at the root. For a Max Heap, a custom Comparator is required.

2. How Elements are Stored and Accessed

Adding an Element (`offer()` / `add()`)

When add() or offer() is called:

The element is inserted at the next available position in the array.
Heapify-up (percolate up) is performed to maintain the heap order.
If the array is full, it resizes dynamically.

Example:

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(30);
pq.add(10);
pq.add(20);
System.out.println(pq); // Output: [10, 30, 20] (Heap structure, not sorted order)

Retrieving the Highest Priority Element (`peek()`)

The element at index 0 is always the smallest (or highest priority) element:

System.out.println(pq.peek()); // Output: 10

Removing an Element (`poll()`)

When poll() is called:

The root element (smallest priority) is removed.
The last element replaces the root.
Heapify-down (percolate down) is performed to maintain the heap property.

Example:

pq.poll();
System.out.println(pq); // Output: [20, 30]

3. Internal Working of Heap in PriorityQueue

Binary Heap Representation

PriorityQueue uses a complete binary tree stored in an array:

        10
       /  \ 
     30    20

Heap Operations

Insertion (Heapify-Up): The newly added element moves up until the heap property is restored.
Deletion (Heapify-Down): The root element is replaced and moved down to restore heap order.

Resizing Mechanism

The default initial size is 11.
When full, the size increases by 1.5x.
The elements are copied to a new larger array.

4. Performance Analysis

Operation	Time Complexity
Add Element	`O(log n)`
Get Min/Max (`peek()`)	`O(1)`
Remove Element	`O(log n)`
Iteration	`O(n log n)`

Comparison with Other Collections

Feature	PriorityQueue (`Heap`)	TreeSet (`Balanced Tree`)	LinkedList (`Queue`)
Maintains Order	✅ Heap Order	✅ Sorted Order	❌ FIFO Order
Performance	⚡ Faster (`O(log n)`)	⏳ Slower (`O(log n)`)	🔄 Slower (`O(n)`)
Best Use Case	Priority-Based Retrieval	Sorted Unique Elements	Standard Queue Processing

5. Use Cases of PriorityQueue

Task Scheduling: Where tasks with higher priority should be executed first.
Graph Algorithms: Used in Dijkstra’s Shortest Path Algorithm and Prim’s MST.
Merging K-Sorted Lists: Efficiently merges multiple sorted lists.

Example: Custom Comparator (Max Heap)

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.add(10);
maxHeap.add(20);
maxHeap.add(5);
System.out.println(maxHeap.poll()); // Output: 20 (Largest element)

6. Key Takeaways

✔ PriorityQueue is a binary heap-based implementation.

✔ Uses heap property to maintain priority order (Min Heap by default).

✔ Provides efficient O(log n) insertion and removal.

✔ Not suitable for ordered iteration (does not guarantee sorted order).

✔ Use PriorityQueue for priority-based scheduling and processing.

Understanding the internal working of PriorityQueue helps in selecting the right data structure for tasks requiring efficient priority-based retrieval.

Java