Deep Dive (java.util) - PriorityQueue

"A queue that doesn't play fair — the 'most important' element always gets served first."

PriorityQueue is backed by a binary min-heap stored in a plain array. This deep dive explains heap structure, sift-up/sift-down operations, and why it's the go-to for scheduling and top-K problems.

---

What is PriorityQueue, Really?

PriorityQueue is a min-heap stored in an array. The smallest element (according to natural ordering or a provided Comparator) is always at the front.

Key facts:

• NOT a FIFO queue — it's a priority queue

• The head (peek()/poll()) is always the minimum element

• Implemented as a binary min-heap in an array

• Does NOT sort all elements — only guarantees the minimum is at the top

• NOT thread-safe (use PriorityBlockingQueue for concurrency)

---

The Binary Heap — Array as a Tree

A binary heap is a complete binary tree stored in an array. The tree structure is implicit — no node objects, no pointers. Just math.

transient Object[] queue; // The heap array

// For node at index i:
// Parent:      (i - 1) / 2   (integer division)
// Left child:  2 * i + 1
// Right child: 2 * i + 2

The Heap Property: Every parent is ≤ both its children (for a min-heap). This guarantees the root (index 0) is always the minimum.

---

How offer() Works — Sift Up

When you add an element, it's placed at the end of the array, then "sifted up" to its correct position:

public boolean offer(E e) {
    int i = size;
    if (i >= queue.length)
        grow(i + 1);       // Resize array (similar to ArrayList)
    siftUp(i, e);
    size = i + 1;
    return true;
}

private void siftUp(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;  // Parent index
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)
            break;                   // Heap property satisfied
        queue[k] = e;                // Swap parent down
        k = parent;                  // Move up
    }
    queue[k] = x;
}

Time complexity: O(log n) — at most log₂(n) swaps up the tree.

---

How poll() Works — Sift Down

poll() removes and returns the minimum (root). It replaces the root with the last element, then sifts it down:

public E poll() {
    final Object[] es = queue;
    final E result = (E) es[0];      // The minimum
    final int n = --size;
    final E x = (E) es[n];           // Last element
    es[n] = null;                     // Clear last slot
    if (n > 0)
        siftDown(0, x);              // Move last element to root, sift down
    return result;
}

private void siftDown(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
        int child = (k << 1) + 1;    // Left child
        Object c = queue[child];
        int right = child + 1;
        
        // Pick the smaller child
        if (right < size && comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        
        if (comparator.compare(x, (E) c) <= 0)
            break;                   // Heap property satisfied
        
        queue[k] = c;                // Swap smaller child up
        k = child;
    }
    queue[k] = x;
}

Time complexity: O(log n) — at most log₂(n) swaps down the tree.

---

How peek() Works

Trivially simple — the minimum is always at index 0:

public E peek() {
    return (E) queue[0]; // O(1) — it's always the root!
}

---

Custom Ordering with Comparator

By default, PriorityQueue uses natural ordering (elements must implement Comparable). You can provide a Comparator for custom ordering:

// Default: min-heap (smallest first)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(30);
minHeap.offer(10);
minHeap.offer(20);
minHeap.poll(); // 10 (smallest)

// Max-heap: largest first
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(30);
maxHeap.offer(10);
maxHeap.offer(20);
maxHeap.poll(); // 30 (largest)

// Custom: by string length
PriorityQueue<String> byLength = new PriorityQueue<>(
    Comparator.comparingInt(String::length)
);
byLength.offer("Banana");
byLength.offer("Fig");
byLength.offer("Cherry");
byLength.poll(); // "Fig" (shortest)

---

Building a Heap — heapify()

When constructing a PriorityQueue from an existing collection, it uses heapify — a bottom-up process that's faster than adding elements one by one:

// O(n) heapify — faster than n × O(log n) adds
PriorityQueue<Integer> pq = new PriorityQueue<>(Arrays.asList(5, 3, 8, 1, 7, 2, 4));

private void heapify() {
    final Object[] es = queue;
    int n = size, i = (n >>> 1) - 1; // Start from last non-leaf
    for (; i >= 0; i--)
        siftDown(i, (E) es[i]);      // Sift down each non-leaf
}

The key insight: half the nodes are leaves and need zero work. Each higher level has fewer nodes but more work, and the sum converges to O(n).

---

Performance Characteristics

Operation	Time Complexity	Notes
offer(e) / add(e)	O(log n)	Sift up
poll()	O(log n)	Sift down
peek()	O(1)	Root is always the min
remove(Object)	O(n)	Linear search + sift
contains(Object)	O(n)	Linear search
heapify (constructor)	O(n)	Bottom-up construction
size()	O(1)	Stored field

Warning: remove(Object) and contains(Object) are O(n) because the heap property only helps find the minimum — to find an arbitrary element, you must scan the entire array.

---

Use Cases

Task Scheduling

record Task(String name, int priority) implements Comparable<Task> {
    public int compareTo(Task other) {
        return Integer.compare(this.priority, other.priority);
    }
}

PriorityQueue<Task> scheduler = new PriorityQueue<>();
scheduler.offer(new Task("Email", 3));
scheduler.offer(new Task("Deploy", 1));   // Highest priority
scheduler.offer(new Task("Meeting", 2));

scheduler.poll(); // Deploy (priority 1 — most urgent)
scheduler.poll(); // Meeting (priority 2)
scheduler.poll(); // Email (priority 3)

Top-K Elements

// Find the 3 largest numbers from a stream
PriorityQueue<Integer> topK = new PriorityQueue<>(3); // min-heap of size K

for (int num : new int[]{5, 1, 9, 3, 7, 2, 8, 4, 6}) {
    topK.offer(num);
    if (topK.size() > 3)
        topK.poll();   // Remove the smallest (keeps only 3 largest)
}
// topK contains: {7, 8, 9}

Merge K Sorted Lists

// Merge K sorted lists into one sorted stream
PriorityQueue<int[]> pq = new PriorityQueue<>(
    Comparator.comparingInt(a -> a[0])  // Compare by current value
);

// Add first element of each list
// pq entry: [value, listIndex, elementIndex]
pq.offer(new int[]{lists[0][0], 0, 0});
pq.offer(new int[]{lists[1][0], 1, 0});
pq.offer(new int[]{lists[2][0], 2, 0});

while (!pq.isEmpty()) {
    int[] min = pq.poll();  // Always get the globally smallest
    result.add(min[0]);
    // Add next element from same list
    if (min[2] + 1 < lists[min[1]].length) {
        pq.offer(new int[]{lists[min[1]][min[2]+1], min[1], min[2]+1});
    }
}

---

Common Pitfalls

Pitfall 1: Expecting Sorted Iteration

// ❌ WRONG: Iterator does NOT return elements in priority order!
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 3, 2, 4));
for (int n : pq) {
    System.out.print(n + " "); // Could be: 1 2 3 5 4 — NOT fully sorted!
}
// The heap property only guarantees the ROOT is the minimum.
// Internal array order ≠ sorted order.

// ✅ CORRECT: Use poll() to get sorted output
while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " "); // 1 2 3 4 5 — sorted!
}

Pitfall 2: Not Thread-Safe

// ❌ PriorityQueue is NOT thread-safe
// ✅ Use PriorityBlockingQueue for concurrent access
PriorityBlockingQueue<Task> threadSafe = new PriorityBlockingQueue<>();

Pitfall 3: Updating Priorities

// ❌ Changing an element's priority after insertion breaks the heap!
Task task = new Task("Email", 3);
pq.offer(task);
task.priority = 0;  // Heap doesn't know about this change!
pq.poll();          // May NOT return the updated task!

// ✅ FIX: Remove and re-add
pq.remove(task);
task.priority = 0;
pq.offer(task);

---

Summary

The one-liner: PriorityQueue is a binary min-heap in an array with O(log n) insert/remove-min and O(1) peek — perfect for scheduling and top-K problems, but beware that iteration order is NOT sorted.