Max/Min Heap - Algorithms and Problem SolvingAlgorithms and Problem Solving

Max/Min Heap - Algorithms and Problem SolvingAlgorithms and Problem Solving

Heap is a special data structure that has a shape of a complete binary tree (except possibly the deepest internal node) with a special property. We call it 'Heap Property'.

Heap property
All nodes are either greater than or equal to (for max heap) or less than or equal to (for min heap) each of its children.
Both the insert and extract (remove) operations modify the heap in O(log n) time to satisfy

1. The shape property Form a complete binary tree by adding or removing from the end of the heap.
2. The heap property Heap property is maintained by heapify the position of insert or delete i.e. traversing up or down the heap to maintain the order between parent and child.

Insert

1. Add the element to the end of the heap.
2. Maintain the heap property between parent and child recursively – lets call it heapify operation. If parent>=both children for max heap (i.e. parent<=both children for min heap) then stop.
3. If not, swap the max child for max heap (or min child for min heap) with its parent and recurse to the previous step (heapify).

Extract

1. Swap the root (element at 0) of the heap with the last element.
2. Remove the last element by shrinking the heap size by 1.
3. Maintain the heap property by doing heapify as described above; if they are in the correct order, stop.

protected abstract class Heap<T extends Comparable<T>> {

    private final ArrayList<T> A;
    private int nextSlot;
    private static final int MAX_HEAPSIZE = 1000;

    public abstract boolean isSatisfied(T a, T b);

    public Heap(final ArrayList<T> A) {
        this.A = A;
        this.nextSlot = 0;
    }

    public int left(final int i) {
        return 2 * i + 1;
    }

    public int right(final int i) {
        return 2 * i + 2;
    }

    public int parent(final int i) {
        return i > 0 ? (i - 1) / 2 : -1;
    }

    public int size() {
        return nextSlot;
    }

    private void swap(final int i, final int j) {
        if (i != j) {
            final T temp = A.get(i);
            A.set(i, A.get(j));
            A.set(j, temp);
        }
    }

    public void heapify(final int index) {
        if (index > nextSlot) {
            return;
        }
        final int p = parent(index);
        while (p >= 0 && !isSatisfied(A.get(p), A.get(index))) {
            swap(p, index);
            heapify(p);
        }
    }

    public boolean insert(final T key) {
        if (nextSlot < MAX_HEAPSIZE) {
            A.add(nextSlot, key);
            heapify(nextSlot);
            nextSlot++;
            return true;
        } else {
            return false;
        }
    }

    public T extract() {
        if (nextSlot > 0) {
            final T removed = A.get(0);
            swap(0, nextSlot - 1);
            nextSlot--;
            heapify(0);

            return removed;
        }
        return null;
    }

    public T top() {
        if (nextSlot > 0) {
            return A.get(0);
        } else {
            return null;
        }
    }
}

public class MaxHeap<T extends Comparable<T>> extends Heap<T> {
    private final Comparator<T> comparator;

    public MaxHeap() {
        super(new ArrayList<T>(10));
        comparator = null;
    }

    public MaxHeap(final Comparator<T> comparator) {
        super(new ArrayList<T>(10));
        this.comparator = comparator;
    }

    public MaxHeap(final int size) {
        super(new ArrayList<T>(size > Heap.MAX_HEAPSIZE ? Heap.MAX_HEAPSIZE : size));
        comparator = null;
    }

    public MaxHeap(final int size, final Comparator<T> comparator) {
        super(new ArrayList<T>(size > Heap.MAX_HEAPSIZE ? Heap.MAX_HEAPSIZE : size));
        this.comparator = comparator;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean isSatisfied(final T a, final T b) {
        if (comparator != null) {
            return comparator.compare(a, b) >= 0 ? true : false;
        }
        return ((Comparable<T>) a).compareTo(b) >= 0 ? true : false;
    }
}

public class MinHeap<T extends Comparable<T>> extends Heap<T> {
    private final Comparator<T> comparator;

    public MinHeap() {
        super(new ArrayList<T>(10));
        comparator = null;
    }

    public MinHeap(final Comparator<T> comparator) {
        super(new ArrayList<T>(10));
        this.comparator = comparator;
    }

    public MinHeap(final int size) {
        super(new ArrayList<T>(size > Heap.MAX_HEAPSIZE ? Heap.MAX_HEAPSIZE : size));
        comparator = null;
    }

    public MinHeap(final int size, final Comparator<T> comparator) {
        super(new ArrayList<T>(size > Heap.MAX_HEAPSIZE ? Heap.MAX_HEAPSIZE : size));
        this.comparator = comparator;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean isSatisfied(final T a, final T b) {
        if (comparator != null) {
            return comparator.compare(a, b) <= 0 ? true : false;
        }
        return ((Comparable<T>) a).compareTo(b) <= 0 ? true : false;
    }
}

Read full article from Max/Min Heap - Algorithms and Problem SolvingAlgorithms and Problem Solving