Java PriorityQueue

Java PriorityQueue

java.util.PriorityQueue<E> breaks the waiting-line contract that every other Queue honours. Elements are not served in arrival order — they are served in priority order. Every poll() call returns the element with the highest priority regardless of when it was inserted. Under the hood this is a binary min-heap: a complete binary tree stored in a flat array where the root is always the smallest element. Understanding the heap is what separates developers who use PriorityQueue confidently from those who accidentally break it.

What Is Java PriorityQueue?

PriorityQueue<E> is a concrete class in java.util that implements Queue<E>. It stores elements in a binary min-heap — a data structure where every parent is smaller than (or equal to) both its children. The practical effect: peek() is always O(1) and returns the current minimum, poll() removes and returns the minimum in O(log n), and insertion via offer() is O(log n).

The diagram below shows where PriorityQueue fits in the Collections hierarchy.

java.lang.Iterable<E>
    └── java.util.Collection<E>
            └── java.util.Queue<E>          ← FIFO contract
                    ├── java.util.Deque<E>
                    │       └── ArrayDeque  ← FIFO/LIFO, arrival order
                    └── java.util.PriorityQueue<E>  ← PRIORITY ORDER (not FIFO)

KEY FACTS:
  Package    : java.util
  Since      : Java 1.5
  Implements : Queue<E>, Collection<E>, Iterable<E>
  Backed by  : binary min-heap in a resizable Object[] array
  Ordering   : natural (Comparable) by default; Comparator-supplied for custom order
  Null       : NOT allowed — compareTo(null) throws NullPointerException
  Duplicates : allowed — equal-priority elements are both stored
  Thread     : NOT thread-safe (use PriorityBlockingQueue for concurrent access)
  Default capacity: 11 elements
  Grow factor : roughly 50% when capacity is exceeded

Basic Overview — The Min-Heap Structure

Every element in a PriorityQueue lives inside a flat Object[] array that represents a complete binary tree. The root is always at index 0 and is always the minimum element.

BINARY MIN-HEAP for [10, 20, 15, 40, 30, 25]:

  ARRAY LAYOUT:
    index:  [ 0  |  1  |  2  |  3  |  4  |  5  ]
    value:  [ 10 | 20  | 15  | 40  | 30  | 25  ]

  TREE VIEW:
              10           ← root = minimum (index 0)
            /    \
          20      15
         /  \    /
        40  30  25

  PARENT-CHILD INDEX RELATIONSHIPS:
    parent(i)     = (i - 1) / 2   (integer division)
    leftChild(i)  = 2 * i + 1
    rightChild(i) = 2 * i + 2

  HEAP PROPERTY:
    array[parent(i)] <= array[i]  for all i > 0
    Every parent is smaller than or equal to both its children.
    This guarantees: array[0] is ALWAYS the minimum element.

  WHAT ITERATION SHOWS (for-each, toString()):
    Traverses the array in index order → NOT sorted order
    [10, 20, 15, 40, 30, 25] — only root is guaranteed to be minimum

When to Use PriorityQueue

The choice between PriorityQueue, ArrayDeque, TreeSet, and LinkedList depends on what "next" means for your use case.

USE PriorityQueue WHEN:
  1. "Always serve the most important element next" regardless of arrival order
     — incident queues (critical bugs before minor bugs)
     — task schedulers (high-priority jobs first)
     — Dijkstra's shortest path (nearest unexplored node first)
     — A* search (best-estimate node first)

  2. Top-K problems: "find the K smallest/largest elements in a dataset"
     — maintain a max-heap of size K → K smallest always inside
     — maintain a min-heap of size K → K largest always inside

  3. Merge K sorted arrays/lists: use a min-heap to always pick the
     smallest current front element across K arrays

  4. Streaming median: maintain two heaps (max for lower half, min for upper half)

CHOOSE ArrayDeque INSTEAD WHEN:
  - Strict FIFO is needed — first received, first processed
  - No priority difference exists between elements

CHOOSE TreeSet INSTEAD WHEN:
  - Sorted unique elements AND range queries (floor, ceiling, headSet) are needed
  - Duplicates must be rejected based on comparison equality

CHOOSE PriorityBlockingQueue INSTEAD WHEN:
  - Multiple producer and consumer threads share the queue
  - PriorityQueue is not thread-safe

DO NOT USE PriorityQueue WHEN:
  - Iteration in sorted order is needed — use TreeSet
  - Random access by index is needed — use ArrayList
  - The order of equal-priority elements must be preserved (FIFO within same priority)
    — PriorityQueue does not guarantee ordering among equal-priority elements

How PriorityQueue Works Internally

Sift-Up — What Happens on offer()

Every offer(element) adds the new element at the end of the array (the next leaf position) and then sifts it up by repeatedly swapping it with its parent until the heap property is restored.

OFFER(8) into existing heap [10, 20, 15, 40, 30, 25]:

  BEFORE:
    array: [10, 20, 15, 40, 30, 25]
    tree:       10
               /  \
             20    15
            / \   /
           40 30 25

  Step 1: append 8 at index 6
    array: [10, 20, 15, 40, 30, 25, 8]
    8 is at index 6, parent = (6-1)/2 = 2, parent value = 15

  Step 2: 8 < 15 → swap 8 and 15
    array: [10, 20, 8, 40, 30, 25, 15]
    8 is now at index 2, parent = (2-1)/2 = 0, parent value = 10

  Step 3: 8 < 10 → swap 8 and 10
    array: [8, 20, 10, 40, 30, 25, 15]
    8 is now at index 0 — it is the root, no parent to check

  AFTER:
    array: [8, 20, 10, 40, 30, 25, 15]
    tree:        8             ← new minimum at root
               /   \
             20     10
            / \    /  \
           40 30  25  15

  Each sift-up comparison moves one level up: O(log n) steps maximum.

Sift-Down — What Happens on poll()

poll() removes the root (minimum element), places the last array element at the root, and sifts it down by repeatedly swapping it with the smaller of its two children until the heap property is restored.

POLL() from heap [8, 20, 10, 40, 30, 25, 15]:

  Step 1: save result = 8 (root)
  Step 2: move last element (15) to root; size--
    array: [15, 20, 10, 40, 30, 25]
    15 is at index 0; children: left=20 (index 1), right=10 (index 2)

  Step 3: 15 > min(20,10)=10 → swap 15 and 10
    array: [10, 20, 15, 40, 30, 25]
    15 is at index 2; children: left=25 (index 5), no right child

  Step 4: 15 < 25 → heap property satisfied, stop

  AFTER:
    array: [10, 20, 15, 40, 30, 25]
    tree:       10
               /  \
             20    15
            / \   /
           40 30 25

  Returns: 8 — the previous minimum.
  Each sift-down comparison moves one level down: O(log n) steps maximum.

Floyd's Heapify — Bulk Construction in O(n)

When you create a PriorityQueue from an existing collection using the PriorityQueue(Collection) constructor, Java does not insert elements one by one. It uses Floyd's heapify algorithm — which builds a valid heap from an arbitrary array in O(n) time, not O(n log n).

FLOYD'S HEAPIFY on arbitrary array [35, 10, 50, 20, 30]:

  Start as a complete binary tree:
         35
        /   \
      10     50
     / \
    20  30

  Process all non-leaf nodes from right to left (index n/2-1 down to 0):
  Last non-leaf: index (5/2 - 1) = 1  (value 10)

  Sift-down index 1 (value 10):
    children: 20 (idx 3), 30 (idx 4)
    10 < min(20,30) → already correct, no swap

  Sift-down index 0 (value 35):
    children: 10 (idx 1), 50 (idx 2)
    35 > min(10,50)=10 → swap 35 and 10
    35 now at index 1: children 20 (idx 3), 30 (idx 4)
    35 > min(20,30)=20 → swap 35 and 20
    35 now at index 3: no children — stop

  RESULT: [10, 20, 50, 35, 30]
  Valid heap — constructed in O(n), not O(n log n)

Core Operations with Examples

offer(), poll(), peek() — Priority Order in Action

Output:
=== Min-heap basics ===
Inserted     : [42, 7, 91, 15, 3, 56]
Internal array: [3, 7, 56, 42, 15, 91]
peek()       : 3
size()       : 6

=== poll() always returns minimum ===
Processing order: 3 7 15 42 56 91

=== Max-heap with Comparator.reverseOrder() ===
peek() : 91
Processing order: 91 56 42 15 7 3

Custom Objects — Comparator-Based Priority

Output:
=== Custom priority — highest urgency first ===
Task     Pri  Description
-------------------------------------------------------
T001     1    Database is unreachable
T002     1    Authentication service down
T003     2    API rate limit alert
T004     2    Slow query degrading performance
T005     3    Memory usage at 85 percent

=== Built from List using Floyd's O(n) heapify ===
List       : [88, 45, 92, 67, 78, 55, 95, 33, 71]
Heap array : [33, 45, 55, 67, 78, 92, 95, 88, 71]
Minimum    : 33

Top-K Elements — The Classic PriorityQueue Pattern

Finding the K smallest or K largest elements from a large dataset is one of the most tested PriorityQueue patterns in product company interviews.

Output:
Dataset: [88, 45, 92, 67, 78, 55, 95, 33, 71, 84, 62, 99, 41]
K = 4

4 smallest : [67, 45, 55, 33]
4 largest  : [92, 95, 88, 99]
4th smallest : 67

Top 3 spend amounts: [22000, 37000, 45000]

Basic Example

Output

peek(): 10
poll(): 10
poll(): 20
poll(): 30

How it works:

1. ›offer() inserts elements in arbitrary order — 30, then 10, then 20 — but PriorityQueue does not store them in insertion order.
2. ›peek() returns 10, the smallest element, because the internal binary min-heap always keeps the minimum at the root, ready to inspect in O(1).
3. ›Each poll() call removes and returns the current smallest element, so repeated poll() calls always come out in ascending order — 10, then 20, then 30 — regardless of the order they were offered.
4. ›This is the core behaviour that distinguishes PriorityQueue from a FIFO Queue: elements are served by priority (smallest first, by default), not by arrival order.

Performance Considerations

O(n) vs O(n log n) construction: Building a PriorityQueue from a Collection via the PriorityQueue(Collection) constructor uses Floyd's heapify and is O(n). Inserting n elements one by one with offer() is O(n log n). When initialising from an existing collection, always use the constructor.

contains() and remove() are O(n): Unlike TreeSet, PriorityQueue has no fast path for membership testing or value-based removal. It must scan the entire array linearly. For workloads that require frequent contains() or targeted remove() by value, combine PriorityQueue with a HashMap to maintain a fast lookup structure alongside the heap.

Thread safety: PriorityQueue is not thread-safe. For concurrent access, use PriorityBlockingQueue from java.util.concurrent — it has the same heap semantics but with a ReentrantLock for thread safety and blocking take() that waits when the queue is empty.

Best Practices

Always include a tiebreaker in Comparator or compareTo(). Two elements where compare(a, b) == 0 are both stored — PriorityQueue allows duplicates — but their relative processing order is undefined. For incident queues, task schedulers, or any use case where arrival order should determine tie resolution, add a secondary comparison field such as a unique ID or creation timestamp: Comparator.comparingInt(Task::priority).thenComparing(Task::id).

Never mutate a field used in priority comparison after insertion. PriorityQueue fixes the heap position at insertion time. Changing the priority field of an element that is already inside the queue corrupts the heap property — the element is in the wrong position and poll() returns incorrect results. The correct escalation pattern is to drain all elements, update the fields, and rebuild the heap with addAll().

For top-K problems, maintain a heap of exactly size K. A max-heap of size K gives you K smallest elements; a min-heap of size K gives you K largest. After each insertion, if heap.size() > k, call poll() to evict the out-of-range element. This keeps memory usage at O(k) rather than O(n) — critical for streaming datasets where n can be millions.

To iterate in priority order, drain a copy — never use for-each on the original. for (T item : priorityQueue) traverses the heap array, not the priority order. If you need to inspect all elements in priority order without destroying the queue: PriorityQueue<T> copy = new PriorityQueue<>(original); while (!copy.isEmpty()) { process(copy.poll()); }. The constructor copy triggers O(n) Floyd's heapify on the copy.

Common Mistakes

Mistake 1 — Expecting for-each to Iterate in Priority Order

Output:
for-each: [10, 20, 30, 50, 40]
poll() order: 10 20 30 40 50

Mistake 2 — Mutating a Priority Field After Insertion

Mistake 3 — Using PriorityQueue When FIFO Within Same Priority Is Required

Mistake 4 — Using offer() in a Loop When Constructor Can Build in O(n)

Interview Questions

Q1. What is PriorityQueue in Java and how does it differ from a regular Queue?

PriorityQueue<E> is a Queue implementation backed by a binary min-heap. Unlike ArrayDeque or LinkedList, which serve elements in FIFO (arrival) order, PriorityQueue always serves the element with the highest priority — by default, the smallest element via natural ordering. offer() and poll() are O(log n) because every insertion triggers a sift-up and every removal triggers a sift-down to restore the heap property. peek() is O(1) because the minimum is always at the root (index 0). Iteration via for-each does NOT traverse in priority order — it traverses the internal heap array.

Q2. How does the binary min-heap work internally in PriorityQueue?

The heap is stored in a flat Object[] array. For any element at index i, its parent is at (i-1)/2, its left child at 2*i+1, and its right child at 2*i+2. The heap property: every parent is smaller than or equal to its children. When offer(e) is called, e is appended at the end (next leaf) and sifted up — repeatedly swapped with its parent until it is no longer smaller than its parent, or it reaches the root. When poll() is called, the root is removed, the last element is placed at the root, and sifted down — repeatedly swapped with the smaller child until both children are larger. Both operations traverse O(log n) levels.

Q3. What is Floyd's heapify algorithm and why does it matter?

Floyd's heapify builds a valid heap from an arbitrary array in O(n) time by processing all non-leaf nodes from right to left, sifting each one down. The reason it is O(n) rather than O(n log n) is mathematical: most nodes in a complete binary tree are near the leaves where sift-down paths are short. When you construct a PriorityQueue from a Collection using the constructor new PriorityQueue<>(collection), Java uses Floyd's algorithm. When you insert elements one by one with offer(), each insertion is O(log n), giving O(n log n) total. For bulk initialisation, the constructor is always faster.

Q4. How do you implement a max-heap using PriorityQueue?

Pass Comparator.reverseOrder() to the constructor: new PriorityQueue<>(Comparator.reverseOrder()). This inverts the natural ordering so the largest element is the root. For custom classes, use a reversed comparator: Comparator.comparingInt(Task::getPriority).reversed(). The internal heap structure is unchanged — only the comparison direction is flipped, so all O(log n) sift-up and sift-down operations still apply correctly.

Q5. How would you find the K largest elements in a stream using PriorityQueue?

Maintain a min-heap of size K. For each incoming element, offer() it into the heap. If heap.size() > K, call poll() to remove the current minimum. After processing all elements, the heap contains exactly the K largest elements — the minimum in the heap is the Kth largest. This approach is O(n log K) time and O(K) space, which is optimal for streaming data where n can be very large. The inverse — K smallest using a max-heap — works symmetrically.

Q6. What happens when you modify a PriorityQueue element's comparison field after insertion?

The heap position is fixed at the time of insertion based on the element's priority value. Changing the priority field after insertion does not trigger any re-heapification — the heap is now inconsistent. The element stays in its old position, violating the heap property for all its ancestors and descendants. Subsequent poll() calls may return elements in incorrect priority order. The correct approach is to drain the entire queue, update the field, and rebuild using addAll(), which triggers Floyd's O(n) heapify.

FAQs

Does PriorityQueue allow null elements?

No. PriorityQueue throws NullPointerException on offer(null). Every insertion requires a compareTo() or Comparator comparison to find the correct heap position. Comparing any element with null throws NullPointerException. If a "no value" sentinel is needed, use Optional<E> as the element type or a dedicated non-null constant.

Can PriorityQueue contain duplicate elements?

Yes. Unlike TreeSet, which treats compare == 0 as "same element" and rejects the duplicate, PriorityQueue stores both. Two elements where compare(a, b) == 0 are both inserted and both available for poll(). Their relative dispatch order among equal-priority elements is heap-implementation-defined — no FIFO guarantee within the same priority level.

Is PriorityQueue the same as a sorted list?

No. The internal array is a heap, not a sorted array. Only the root (index 0) is guaranteed to be the minimum. The rest of the array satisfies the heap property (parent ≤ children) but is not in any particular sorted order. A sorted array would require O(n log n) to build and O(n) to insert while maintaining sorted order. The heap builds in O(n) (Floyd's) and inserts in O(log n), at the cost of not being sortable for free.

What is the difference between PriorityQueue and TreeSet?

Both maintain elements in an ordered fashion, but serve completely different purposes. PriorityQueue allows duplicates, is backed by a binary heap, and provides O(1) peek() and O(log n) poll() for the minimum. It has no fast contains() or remove(e) — both are O(n). TreeSet rejects duplicates, is backed by a Red-Black tree, and provides O(log n) for all operations including contains(), remove(), floor(), and ceiling(). Use PriorityQueue when you only need "next minimum" access and duplicates are expected. Use TreeSet when you need sorted unique elements with range navigation.

Why does PriorityQueue print elements out of order using toString()?

PriorityQueue.toString() delegates to AbstractCollection.toString(), which iterates using the collection's iterator. The iterator traverses the internal heap array in index order (0, 1, 2, ...), which is NOT sorted order. The heap array satisfies the heap property but is not a sorted array. Only the root is guaranteed to be the minimum. This confuses beginners who expect println(pq) to show sorted output.

How do you create a PriorityQueue for String elements in reverse alphabetical order?

Pass a comparator using Comparator.reverseOrder() or Collections.reverseOrder() to the constructor: new PriorityQueue<>(Comparator.reverseOrder()). This creates a max-heap where poll() returns the lexicographically largest string first. For a custom multi-field ordering, compose with thenComparing().

Summary

PriorityQueue<E> is Java's binary min-heap implementation of the Queue interface. Every offer() triggers a sift-up to restore the heap property; every poll() triggers a sift-down. Both are O(log n). peek() is O(1) because the minimum always lives at the root. Creating from a collection uses Floyd's O(n) heapify — always faster than sequential offers.

The three rules that prevent every common PriorityQueue bug: never expect for-each to iterate in priority order, never mutate a priority field after insertion without rebuilding the heap, and always include a tiebreaker in compareTo() or Comparator to ensure stable ordering within equal-priority elements.

The most important interview patterns: max-heap via Comparator.reverseOrder(), K smallest with a max-heap of size K, K largest with a min-heap of size K, and the correct escalation pattern of drain-update-rebuild. These cover the majority of PriorityQueue questions from service-based fresher rounds through product-company technical interviews.

What to Read Next