Java MaxHeap Class

This was taken and modified from http://www.cs.usfca.edu/galles/cs245/lecture/MinHeap.java.html

I should change this to use be more generic sometime.

Right now it's assuming I'm adding Objects of class Link.

Link implements Comparable, and has a constructor where you pass it one String ("max" or "min"). If "max", you assign it the maximum possible value. If "min", you assign it the minimum (for use in MinHeap if you want to create one)


public class MaxHeap {
private Link[] Heap;
private int maxsize;
private int size;

public MaxHeap() { this(100); }

public MaxHeap(int max) {
maxsize = max;
Heap = new Link[maxsize];
size = 0 ;
Heap[0] = new Link("max");
}

private int leftchild(int pos) { return 2*pos; }

private int rightchild(int pos) { return 2*pos + 1; }

private int parent(int pos) { return pos / 2; }

private boolean isleaf(int pos) { return ((pos > size/2) && (pos <= size)); }

private void swap(int pos1, int pos2) {
Link tmp;

tmp = Heap[pos1];
Heap[pos1] = Heap[pos2];
Heap[pos2] = tmp;
}

public void insert(Link elem) {
size++;
if(size >= maxsize-1)
doubleSize();
Heap[size] = elem;
int current = size;

while (Heap[current].compareTo(Heap[parent(current)]) > 0) {
swap(current, parent(current));
current = parent(current);
}
}

public void doubleSize()
{
maxsize = maxsize * 2;
Link[] newHeap = new Link[maxsize];

for(int i=0; i <=size; i++)
newHeap[i] = Heap[i];

Heap = newHeap;
}

public void print() {
int i;
for (i=1; i<=size;i++)
System.out.print(Heap[i] + " ");
System.out.println();
}

public Link removeMax() {
swap(1,size);
size--;
if (size != 0)
pushdown(1);
return Heap[size+1];
}

private void pushdown(int position) {
int largestchild;
while (!isleaf(position)) {
largestchild = leftchild(position);
if ((largestchild < size) && (Heap[largestchild].compareTo(Heap[largestchild+1]) <= 0))
largestchild = largestchild + 1;
if (Heap[position].compareTo(Heap[largestchild]) >= 1) return;
swap(position,largestchild);
position = largestchild;
}
}

public int size() { return size; }
}