Java binary min-heap: sifting, fixed capacity and duplicate priorities

Last updated: 29 Sept 20264 min read

tutorial

A binary min-heap keeps every parent priority no greater than its children so its root supplies a minimum value.

Java 8+. This is a complete program using JDK classes.

Maintain one local relation

A dispatch queue stores integer priorities. Inserting at the next array slot can violate the relation to its parent, so sift-up swaps until that relation is restored. Polling replaces the root with the last member, then sift-down chooses the smaller child.

The array is bounded by a constructor capacity. This implementation rejects a full queue rather than resizing or dropping a job. Equal priorities are retained as separate values, but their original arrival order is not represented; stable job order needs a sequence-number tie-breaker.

Heap order is weaker than complete sorting. A caller that walks this backing array does not receive sorted output. Repeated poll calls produce ascending priorities because each call repairs the root relation before the next removal.

Working program

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class FixedDispatchHeap {
    final int[] priorities; int size;
    FixedDispatchHeap(int capacity) {
        if (capacity < 0) throw new IllegalArgumentException("Negative capacity");
        priorities = new int[capacity];
    }
    void add(int priority) {
        if (size == priorities.length) throw new IllegalStateException("Full heap");
        int position = size++; priorities[position] = priority;
        while (position > 0) {
            int parent = (position-1)/2;
            if (priorities[parent] <= priorities[position]) break;
            swap(parent, position); position = parent;
        }
    }
    void swap(int a, int b) { int old=priorities[a]; priorities[a]=priorities[b]; priorities[b]=old; }
    int poll() {
        if (size == 0) throw new NoSuchElementException("Empty heap");
        int selected=priorities[0]; priorities[0]=priorities[--size]; int position=0;
        while (position < size/2) {
            int child=2*position+1;
            if (child+1<size && priorities[child+1]<priorities[child]) child++;
            if (priorities[position]<=priorities[child]) break;
            swap(position, child); position=child;
        }
        return selected;
    }
    public static void main(String[] args) {
        FixedDispatchHeap queue = new FixedDispatchHeap(4);
        for (int priority : new int[]{7, 4, -2, 4}) queue.add(priority);
        List<Integer> removed=new ArrayList<>();
        while (queue.size>0) removed.add(queue.poll());
        System.out.println(removed);
        try { queue.poll(); }
        catch (NoSuchElementException empty) { System.out.println("Empty rejected"); }
    }
}

Output

[-2, 4, 4, 7]
Empty rejected

Costs and boundaries

Insertion and removal sift through at most O(log n) levels. The fixed backing array occupies O(capacity) space, even when few elements are admitted. Polling all values uses O(n log n) work; the example also allocates O(n) result storage for display.

Common Mistakes

The heap array is not a sorted report.
Capacity rejection is part of this method contract.
Equal priorities do not imply first-in-first-out order.