# 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.

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/28756bfa-e056-450d-b71a-49103d7202db.png align="center")

**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.

```java
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
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/1ab896ec-c088-4096-a228-cc9ed32404e5.png align="center")

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

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/999976b7-f91d-4079-afe7-14a3e537fdc8.png align="center")

* * *

## 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:

```java
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;
}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/7f2bbb27-7456-45f2-9442-ed55a1427ba5.png align="center")

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/9851b061-6343-4064-8cbb-7324692a4183.png align="center")

**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:

```java
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;
}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/76148f18-05ac-40ab-96a9-8dde040508e5.png align="center")

**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:

```java
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:

```java
// 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)
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/c7f4d3ca-4265-4286-92c5-5db0cf41cd56.png align="center")

* * *

## 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:

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

```java
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
}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/a72659b4-86cf-4ac4-bce0-443890d08971.png align="center")

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

```java
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

```java
// 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}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/7cfa1e7a-c40a-4640-a23e-986cfcc786e4.png align="center")

### Merge K Sorted Lists

```java
// 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

```java
// ❌ 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

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

### Pitfall 3: Updating Priorities

```java
// ❌ 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

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/3daa728c-53eb-4072-80b4-362cef676f40.png align="center")

**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.