Back to Study Material Java

PriorityQueue in Java

PriorityQueue in Java is a min-heap by default, meaning the element with the smallest natural ordering is always at the head of the queue. Internally it us...

PriorityQueue in Java

Binary Heap Under the Hood

PriorityQueue in Java is a min-heap by default, meaning the element with the smallest natural ordering is always at the head of the queue. Internally it uses a zero-indexed array to represent a complete binary tree: the element at index i has children at 2i+1 and 2i+2, and a parent at (i-1)/2. This compact array representation avoids the pointer overhead of a true tree structure.

When you offer an element, it is placed at the next available position (the end of the array) and then bubbles up by repeatedly swapping with its parent until the heap property is restored. This sift-up operation is O(log n). When you poll the minimum, the root is removed, the last element is placed at the root, and it sinks down by swapping with the smaller child until the heap property is restored. This sift-down is also O(log n). The peek operation returns the root without modification in O(1).

The heapify operation used in the constructor that accepts a Collection completes in O(n) time, which is faster than inserting each element individually at O(n log n).

Custom Ordering with Comparator

To create a max-heap or define custom priority, pass a Comparator to the constructor. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); now poll returns the largest element. For objects, PriorityQueue<Task> pq = new PriorityQueue<>(Comparator.comparingInt(t -> t.priority)); orders tasks by their priority field.

PriorityQueue does not guarantee any particular order when iterating with a for-each loop or converting to an array. The heap structure only guarantees that poll always returns the current minimum (or maximum with a reversed comparator). If you need a sorted traversal, drain the queue entirely: while (!pq.isEmpty()) System.out.println(pq.poll());

PriorityQueue does not permit null elements because comparison with null would throw a NullPointerException during sift operations.

Classic Applications and Interview Tip

PriorityQueue is the data structure behind Dijkstra's shortest path algorithm, the A* pathfinding algorithm, and the merge of k sorted arrays. For the k-sorted-merge problem: create a min-heap seeded with the first element of each array, then repeatedly poll the minimum and push the next element from whichever array the polled element came from. Total time is O(n log k) where n is total elements and k is the number of arrays.

Another frequent use is finding the k-th largest element. Maintain a min-heap of size k. For each new number, add it; if the heap exceeds k elements, poll the minimum. After processing all elements, the heap's root is the k-th largest.

An interview tip: when asked about PriorityQueue limitations, mention that it is not thread-safe. The concurrent alternative is PriorityBlockingQueue from java.util.concurrent, which provides the same heap semantics with blocking take semantics when empty. Also note that PriorityQueue does not support O(log n) decrease-key operations without removing and reinserting, which matters for advanced graph algorithm implementations.