PriorityQueue and binary heaps

Think of it as a hospital triage desk, not a supermarket line. People still arrive one by one, but the next person called is the most urgent case according to the triage rule.

For this lesson, we'll focus on the concrete Java 21 PriorityQueue: the array-backed binary min-heap, index math, offer, poll, peek, comparator-based max-heaps, growth, nulls, stability, and the task-manager-by-priority scenario interviewers like. We will mention Dijkstra and merging K sorted lists because they are heap-shaped problems, but Top-K has its own lesson: Top-K with a heap.

01Picture it first: a tournament bracket stored flat

A binary heap looks like a small tournament bracket. Each parent has priority no worse than its children, so the best item is always at the root. Java stores that tree in a flat Object[], which is why there are no node objects or left/right references.

The picture below is the one to keep in your head. The tree shape is implicit in the array indexes.

Fig. 1

A binary min-heap shown as both a tree and an array, where parent i has children 2i+1 and 2i+2 and the smallest value is at index 0

Notice what the heap does not promise. A parent is no larger than its children, but siblings are not sorted against each other, and the left subtree is not globally smaller than the right subtree. That is enough to find the minimum quickly, not enough to iterate in sorted order.

02PriorityQueue under the hood

PriorityQueue keeps its elements in an Object[] queue and a size. The default initial capacity is 11. The array grows when needed, but the logical heap is only the first size slots.

import java.util.Arrays;
import java.util.PriorityQueue;

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(40);
queue.offer(10);
queue.offer(30);
queue.offer(5);

System.out.println(queue.peek());              // 5
System.out.println(queue);                     // one heap-shaped order, not a sorted contract

while (!queue.isEmpty()) {
    System.out.print(queue.poll() + " ");      // 5 10 30 40
}

offer(5) appends at the first free slot, then compares with its parent. Starting from [10, 40, 30], 5 lands at index 3. Its parent is index 1 (40), so they swap. Now 5 is at index 1, whose parent is index 0 (10), so they swap again. The root becomes 5.

Notice three things:

• peek() reads queue[0], so it is O(1).
• poll() repeatedly returns sorted values because each call repairs the heap before the next one.
• toString() and iteration walk the internal array. That order is not sorted and should not be used as a sorted result.

Here is a tiny heap implementation with the same index math. I like showing this version because it removes the API surface and leaves the invariant visible.

import java.util.ArrayList;
import java.util.List;

final class IntMinHeap {
    private final List<Integer> heap = new ArrayList<>();

    void offer(int value) {
        heap.add(value);
        siftUp(heap.size() - 1);
    }

    int peek() {
        if (heap.isEmpty()) throw new IllegalStateException("empty heap");
        return heap.get(0);
    }

    int poll() {
        if (heap.isEmpty()) throw new IllegalStateException("empty heap");
        int result = heap.get(0);
        int last = heap.remove(heap.size() - 1);
        if (!heap.isEmpty()) {
            heap.set(0, last);
            siftDown(0);
        }
        return result;
    }

    private void siftUp(int index) {
        int value = heap.get(index);
        while (index > 0) {
            int parent = (index - 1) >>> 1;
            int parentValue = heap.get(parent);
            if (parentValue <= value) break;
            heap.set(index, parentValue);
            index = parent;
        }
        heap.set(index, value);
    }

    private void siftDown(int index) {
        int value = heap.get(index);
        int half = heap.size() >>> 1; // first leaf index is size / 2
        while (index < half) {
            int left = (index << 1) + 1;
            int right = left + 1;
            int child = left;
            int childValue = heap.get(left);

            if (right < heap.size() && heap.get(right) < childValue) {
                child = right;
                childValue = heap.get(right);
            }
            if (value <= childValue) break;
            heap.set(index, childValue);
            index = child;
        }
        heap.set(index, value);
    }
}