PriorityQueue

A queue optimized for fast access to the highest-priority element.

Context

Priority Queue is a data structure that always exposes the element with the highest priority (minimum or maximum) in O(1) time, while maintaining O(log n) insertion and removal.

It is most commonly implemented as a binary heap, which is a complete binary tree stored in a flat array.

Two variants exist:

• Min-Heap: the smallest element is at the root; every parent is ≤ its children.
• Max-Heap: the largest element is at the root; every parent is ≥ its children.

The “complete” part matters: the tree is always filled level-by-level, left-to-right. This invariant is what allows array storage and simple index math.

A classic real-world use is thread scheduling with ageing: threads accumulate priority the longer they wait, preventing starvation while still favouring high-priority work.

Core idea

• Store elements in an array representing a complete binary tree
• Insert elements at the end, then heapify up to restore heap order
• Remove only from the root:
  • Replace root with the last element
  • Heapify down to restore order
• Parent/child relationships are computed via index arithmetic:
  • left child: 2 * parent + 1
  • right child: 2 * parent + 2
  • parent: (child - 1) / 2

Implementation

Base Abstract Class

Plenty of logic is very symmetric between MinHeap and MaxHeap, so the abstract class below serves as a baseline.

public abstract sealed class PriorityQueue<T extends Comparable<? super T>> permits MinHeap, MaxHeap {
    protected T[] elements;
    protected int size;

    @SuppressWarnings("unchecked")
    protected PriorityQueue(int initialCapacity) {
        elements = (T[]) new Comparable[initialCapacity];
    }

    public T peek() {
        return isEmpty() ? null : elements[0];
    }

    public T pop() {
        if (isEmpty()) return null;

        var value = elements[0];
        size--;

        if (size == 0) {
            elements[0] = null;
            return value;
        }

        elements[0] = elements[size];
        elements[size] = null;

        heapifyDown(0);

        return value;
    }

    public void insert(T element) {
        resizeIfNecessary();
        elements[size++] = element;

        if (size != 1) heapifyUp(size - 1);
    }

    public boolean isEmpty() { return size == 0; }

    public int size() { return size; }

    /**
     * @param value Value of an element
     * @param parent Value of the parent element
     * @return boolean Indicator whether this element should be swapped with its parent
     */
    protected abstract boolean shouldBubbleUp(T value, T parent);

    /**
     * @param value Value of an element
     * @param child Value of the child element
     * @return boolean Indicator whether this element should be swapped with its child
     */
    protected abstract boolean shouldBubbleDown(T value, T child);

    /**
     * When bubbling down, you must swap with the higher-priority child, not just any child.
     * @param left Index of a left child
     * @param right Index of a right child
     * @return Index of a child that has a higher priority
     */
    protected abstract int chooseSibling(int left, int right);

    private void heapifyUp(int index) {
        if (index == 0) return;

        var parentIndex = getParentIndex(index);
        var parent = elements[parentIndex];
        var value = elements[index];

        if (shouldBubbleUp(value, parent)) {
            swap(parentIndex, index);
            heapifyUp(parentIndex);
        }
    }

    private void heapifyDown(int index) {
        var leftChildIndex = getLeftChildIndex(index);

        if (index >= size || leftChildIndex >= size) return;

        var value = elements[index];
        var childIndex = chooseSibling(leftChildIndex, getRightChildIndex(index));

        if (shouldBubbleDown(value, elements[childIndex])) {
            swap(index, childIndex);
            heapifyDown(childIndex);
        }
    }

    private int getLeftChildIndex(int parentIndex) {
        return 2 * parentIndex + 1;
    }

    private int getRightChildIndex(int parentIndex) {
        return 2 * parentIndex + 2;
    }

    private int getParentIndex(int childIndex) {
        return (childIndex - 1) / 2;
    }

    private void swap(int index1, int index2) {
        var temp = elements[index1];
        elements[index1] = elements[index2];
        elements[index2] = temp;
    }

    private void resizeIfNecessary() {
        if (elements.length == size) {
            var capacity = elements.length * 3 / 2 + 1;
            elements = Arrays.copyOf(elements, capacity);
        }
    }
}

MinHeap

public final class MinHeap<T extends Comparable<? super T>> extends PriorityQueue<T> {
    public MinHeap(int initialCapacity) {
        super(initialCapacity);
    }

    @Override
    protected boolean shouldBubbleUp(T value, T parent) {
        return value.compareTo(parent) < 0;
    }

    @Override
    protected boolean shouldBubbleDown(T value, T child) {
        return value.compareTo(child) > 0;
    }

    @Override
    protected int chooseSibling(int left, int right) {
        if (right >= size) return left;

        var rightValue = elements[right];
        var leftValue = elements[left];

        return leftValue.compareTo(rightValue) < 0 ? left : right;
    }
}

MaxHeap

public final class MaxHeap<T extends Comparable<? super T>> extends PriorityQueue<T> {
    public MaxHeap(int initialCapacity) {
        super(initialCapacity);
    }

    @Override
    protected boolean shouldBubbleUp(T value, T parent) {
        return value.compareTo(parent) > 0;
    }

    @Override
    protected boolean shouldBubbleDown(T value, T child) {
        return value.compareTo(child) < 0;
    }

    @Override
    protected int chooseSibling(int left, int right) {
        if (right >= size) return left;

        var rightValue = elements[right];
        var leftValue = elements[left];

        return leftValue.compareTo(rightValue) > 0 ? left : right;
    }
}