Java PriorityQueue Internals: Building a Min-Heap Array from Scratch

Suppose you are building a hospital emergency room triage system.

Patients arrive in random order. A patient with a minor headache arrives at 10:00 AM. A patient experiencing severe chest pain arrives at 10:05 AM.

A standard FIFO queue would treat the headache patient first because they arrived five minutes earlier. That is unacceptable in an emergency room. The system must process patients by priority score, regardless of arrival order.

If you sort an array on every arrival, insertions take $O(N)$ time. If you use a Red-Black tree, every node requires object pointers and color tracking overhead.

Java’s PriorityQueue uses a Min-Heap array to deliver $O(1)$ top priority access and $O(\log N)$ insertions/removals with zero object pointer overhead.

---

Representing a Binary Tree in a Flat Array

A Min-Heap is a complete binary tree where every parent node has a value smaller than or equal to its children.

               [ 10 ]                  Index Array Representation:
              /      \                 [ 10 | 15 | 20 | 40 | 50 | 100 | 30 ]
        [ 15 ]        [ 20 ]             0    1    2    3    4     5    6
       /      \      /      \
   [ 40 ]   [ 50 ] [ 100 ]  [ 30 ]

Because the tree is completely filled at every level from left to right, we store tree nodes inside a flat array without node pointer objects.

For any node at index $i$:

$\text{Left Child} = 2i + 1$

$\text{Right Child} = 2i + 2$

$\text{Parent} = \frac{i - 1}{2}$

---

The siftUp Operation (Insertion)

When a new element is offered to the priority queue:

1. Append the element to the end of the array (bottom of the tree).
2. Compare the element against its parent.
3. If the element is smaller than its parent, swap them.
4. Repeat step 3 moving up until the heap invariant is restored.

INSERT 5 into existing heap [ 10, 15, 20 ]:

Step 1: Append 5 at end       --> [ 10, 15, 20, 5 ] (Index 3)
Step 2: Parent is 15 (Index 1)--> 5 < 15, Swap! -> [ 10, 5, 20, 15 ]
Step 3: Parent is 10 (Index 0)--> 5 < 10, Swap! -> [ 5, 10, 20, 15 ]
Heap invariant restored in O(log N) steps.

---

The siftDown Operation (Removal)

When poll() removes the top priority item (index 0):

1. Replace index 0 with the last element in the array.
2. Compare index 0 against its smallest child.
3. If index 0 is larger than its smallest child, swap them.
4. Repeat step 3 moving down the tree until the heap invariant is restored.

---

Complete MyPriorityQueue<T> Implementation

import java.util.Arrays;
import java.util.Comparator;

public class MyPriorityQueue<T> {
    private Object[] queue;
    private int size = 0;
    private final Comparator<? super T> comparator;

    public MyPriorityQueue() {
        this(11, null);
    }

    public MyPriorityQueue(int initialCapacity, Comparator<? super T> comparator) {
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

    public void offer(T e) {
        if (e == null) throw new NullPointerException();
        int i = size;
        if (i >= queue.length) {
            grow(i + 1);
        }
        size = i + 1;
        if (i == 0) {
            queue[0] = e;
        } else {
            siftUp(i, e);
        }
    }

    @SuppressWarnings("unchecked")
    public T poll() {
        if (size == 0) return null;
        int s = --size;
        T result = (T) queue[0];
        T x = (T) queue[s];
        queue[s] = null;
        if (s != 0) {
            siftDown(0, x);
        }
        return result;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        return (size == 0) ? null : (T) queue[0];
    }

    @SuppressWarnings("unchecked")
    private void siftUp(int k, T x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (compare(x, (T) e) >= 0) break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }

    @SuppressWarnings("unchecked")
    private void siftDown(int k, T x) {
        int half = size >>> 1; // loop while node has at least one child
        while (k < half) {
            int child = (k << 1) + 1; // assume left child is smallest
            Object c = queue[child];
            int right = child + 1;
            if (right < size && compare((T) c, (T) queue[right]) > 0) {
                child = right;
                c = queue[child];
            }
            if (compare(x, (T) c) <= 0) break;
            queue[k] = c;
            k = child;
        }
        queue[k] = x;
    }

    @SuppressWarnings("unchecked")
    private int compare(T a, T b) {
        return (comparator != null) 
            ? comparator.compare(a, b) 
            : ((Comparable<? super T>) a).compareTo(b);
    }

    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1));
        queue = Arrays.copyOf(queue, newCapacity);
    }

    public int size() {
        return size;
    }
}

---

Quick Summary

• Min-Heaps store binary trees inside contiguous flat arrays using index math.
• peek() fetches the minimum item in $O(1)$ constant time.
• offer() and poll() restore heap invariants in $O(\log N)$ time using siftUp and siftDown.

References & Further Reading

1. OpenJDK. JEP 155: Concurrency Updates (JDK 8 ConcurrentHashMap Redesign). OpenJDK JEP Standard.
2. OpenJDK Repository. OpenJDK 21 Source Code: java.util.concurrent.ConcurrentHashMap. GitHub.
3. Herlihy, M., & Shavit, N. (2012). The Art of Multiprocessor Programming. Morgan Kaufmann.

---