A max-heap implements a priority queue using a complete binary tree where each parent dominates its descendants. The root contains the maximum value, and the tree fills all level except possibly the deepest, which populates from left to right. This structure enables logarithmic time complexity for insertion and removal operations.

Structure Definition

The underlying representation uses a dynamic array where parent-child relationships derive from indices. For a node at position $i$, the left child resides at $2i + 1$, the right at $2i + 2$, and the parent at $\lfloor (i - 1) / 2 \rfloor$.

public class PriorityHeap<T extends Comparable<T>> {
    private T[] container;
    private int count;
    private final int limit;

    @SuppressWarnings("unchecked")
    public PriorityHeap(int capacity) {
        this.limit = capacity;
        this.container = (T[]) new Comparable[capacity];
        this.count = 0;
    }

    public boolean isFull() {
        return count == limit;
    }

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

Element Insertion via Percolation

Adding an element requires preserving the completeness property and the dominance invariant. The algorithm places the new item at the first available array position (the leftmost open slot in the bottom tree level), then repeatedly exchanges it with its encestor until the parent exceeds or equals the item's value.

public void insert(T value) {
    if (isFull()) {
        throw new IllegalStateException("Heap capacity exceeded");
    }
    
    int slot = count++;
    while (slot > 0) {
        int ancestor = (slot - 1) >>> 1;  // equivalent to (slot - 1) / 2
        if (container[ancestor].compareTo(value) >= 0) {
            break;
        }
        container[slot] = container[ancestor];
        slot = ancestor;
    }
    container[slot] = value;
}

The traversal upward continues until either reaching the root or finding a parent with greater priority. Each shift operation moves a parent down to the child's former position, effectively creating a vacancy that migrates toward the root.

Root Extraction and Restoration

Removal exclusively targets the root element. After capturing the maximum value, the algorithm moves the last array element (the rightmost node in the lowest level) to the vacated root position. This maintains completeness but likely violates the heap ordering. A downward percolation corrects this by repeatedly swapping the displaced element with its larger child until both children are smaller or the element becomes a leaf.

public T extract() {
    if (isEmpty()) {
        return null;
    }
    
    T maximum = container[0];
    T candidate = container[--count];
    container[count] = null;
    
    int position = 0;
    while (true) {
        int left = (position << 1) + 1;
        if (left >= count) break;  // No children
        
        int dominant = left;
        int right = left + 1;
        if (right < count && container[right].compareTo(container[left]) > 0) {
            dominant = right;
        }
        
        if (candidate.compareTo(container[dominant]) >= 0) {
            break;
        }
        
        container[position] = container[dominant];
        position = dominant;
    }
    
    container[position] = candidate;
    return maximum;
}

During the sift-down process, the algorithm compares the displaced value against both offspring, selecting the larger child for the exchange. This ensures the parent-child dominance relationship re-establishes correctly at each level.