Binary Heaps - part two

So, let's go ahead and flesh out the BinaryHeap abstract class I put together in the last post.  You'll notice a few things have changed.  For one, I've decided to make heapify a private method.  I was thinking about potential DRY violations in MinHeap and MaxHeap implementations.  The heapify methods will be identical except for how we treat the return value of the compareTo methods.  The BinaryHeap abstract class's constructors now require a sign argument - this will be the value against which those return values will be compared.

I've also added a constructor that takes the contents of a Java Collection and adds it to the heap en masse, for convenience and efficiency.

Something to remember here when implementing remove: make sure that the last element of the heap is added to the top of the heap, not swapped with that element.  Using swap is almost guaranteed to break the heap property constraint!  This took me a while to debug.

	package heap;
	import java.util.ArrayList;
	import java.util.Collection;
	public abstract class BinaryHeap<T extends Comparable<T>> {
	private ArrayList<T> theHeap;
	private final int sign;
	protected final int left(int i) { return (i << 1) + 1; }
	protected final int right(int i) { return (i << 1) + 2; }
	protected final int parent(int i) { return ((i - 1) >> 1); }
	private void heapify(int i) {
	int j = i;
	int l = left(i);
	int r = right(i);
	if(l < theHeap.size() && (sign == theHeap.get(l).compareTo(theHeap.get(j))))
	j = l;
	if(r < theHeap.size() && (sign == theHeap.get(r).compareTo(theHeap.get(j))))
	j = r;
	if(j != i) {
	swap(i, j);
	heapify(j);
	}
	}
	protected BinaryHeap(int sign) {
	this.sign = sign;
	theHeap = new ArrayList<T>();
	}
	protected BinaryHeap(int sign, Collection<T> contents) {
	this.sign = sign;
	theHeap = new ArrayList<T>(contents);
	for(int i = 1 + theHeap.size() / 2; i >= 0; i--) {
	heapify(i);
	}
	}
	public int size() {
	return theHeap.size();
	}
	private void swap(int i, int j) {
	T temp = theHeap.get(j);
	theHeap.set(j, theHeap.get(i));
	theHeap.set(i, temp);
	}
	public void insert(T t) {
	theHeap.add(t);
	int i = theHeap.size() - 1;
	int p = parent(i);
	while(i > 0 && (sign == theHeap.get(i).compareTo(theHeap.get(p)))) {
	swap(i, p);
	i = p;
	p = parent(i);
	}
	}
	public T remove() {
	T result = null;
	if(theHeap.size() > 0) {
	result = theHeap.remove(0);
	if(theHeap.size() > 1) {
	theHeap.add(0, theHeap.remove(theHeap.size() -1));
	heapify(0);
	}
	}
	return result;
	}
	@Override
	public String toString() {
	return theHeap.toString();
	}
	}

view raw BinaryHeap.java hosted with ❤ by GitHub

	package heap;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collection;
	public class MaxHeap<T extends Comparable<T>> extends BinaryHeap<T> {
	public MaxHeap() {
	super(1);
	}
	public MaxHeap(Collection<T> contents) {
	super(1, contents);
	}
	}

view raw MaxHeap.java hosted with ❤ by GitHub

	package heap;
	import java.util.Collection;
	public class MinHeap<T extends Comparable<T>> extends BinaryHeap<T> {
	public MinHeap() {
	super(-1);
	}
	public MinHeap(Collection<T> contents) {
	super(-1, contents);
	}
	}

view raw MinHeap.java hosted with ❤ by GitHub