Algorithms
Max/Min Heap
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
- The shape property Form a complete binary tree by adding or removing from the end of the heap.
- 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
- Add the element to the end of the heap.
- 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.
- 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
- Swap the root (element at 0) of the heap with the last element.
- Remove the last element by shrinking the heap size by 1.
- Maintain the heap property by doing heapify as described above; if they are in the correct order, stop.
Both are O(n) operation. Below, I have tried to implement a generic version max/min heap. In order to make a heap with primitive type make sure to use the corresponding object class as the type. For example, for int type data we need to use Integer as the generic type. This is because I restricted the generic type only to an object that is comparable (i.e. implemented comparable interface or explicitly provided a comparator). Integer, Long, Double, Character etc. classes implemented the Comparable interface (i.e. compareTo (other) method) for natural ordering of the corresponding primitive type data. To use the heap libraries with custom object either –
- Either, implement the Comparable interface and provide compareTo(other) implementation for natural order (i.e. ascending order). That is,
compareTo(other) = 0 if this == other compareTo(other) = 1 if this > other compareTo(other) = -1 if this < other - Or, provide to the constructor a customized Comparator interface implementation with the compare(o1, o2) method implemented for ascending order. That is,
compare(o1, o2) = 0 if o1 == o2 compare(o1, o2) = 1 if o1 > o2 compare(o1, o2) = -1 if o1 < o2
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;
}
}