Creating and Using a Heap. Index out of Bounds
Hey guys, I'm currently trying to build and use a heap so I created the two following classes.
Code java:
import java.util.*;
public class MyHeap<E extends Comparable<E>>
{
private int size = 0;
private ArrayList<E> heap = new ArrayList<E>();
public void add(E data)
{
heap.add(size, data);
size++;
reheapup(size-1);
}
public E remove()
{
E temp = heap.get(0);
heap.set(0, heap.get(size-1));
size--;
reheapDown(0);
return temp;
}
private void reheapup(int n)
{
if(n==0) return;
E curr = heap.get(n);
E parent = heap.get((n-1)/2);
if (curr.compareTo(parent) > 0) return;
heap.set(n, parent);
heap.set((n-1)/2, curr);
reheapup((n-1)/2);
}
private void reheapDown(int n)
{
if (n >= size) return;
if (2*n+2 < size)
{
E curr = heap.get(n);
E left = heap.get(2*n+1);
E right = heap.get(2*n+2);
if (curr.compareTo(left) > 0 || curr.compareTo(right) > 0)
{
if(left.compareTo(right) < 0)
{
heap.set(n, left);
heap.set(2*n+1, curr);
reheapDown(2*n+1);
}
else
{
heap.set(n, right);
heap.set(2*n+2, curr);
reheapDown(2*n+2);
}
}
}
else
{
E curr = heap.get(n);
E left = heap.get(2*n+1);
if(curr.compareTo(left) > 0)
{
heap.set(n, left);
heap.set(2*n+1, curr);
}
}
}
}
Code java:
public class DriverP07
{
public static void main(String[] args)
{
MyHeap stringHeap = new MyHeap();
MyHeap integerHeap = new MyHeap();
//int temp;
//String s;
integerHeap.add(1);
integerHeap.add(2);
integerHeap.add(3);
integerHeap.add(4);
integerHeap.add(5);
integerHeap.add(6);
integerHeap.add(7);
integerHeap.add(8);
integerHeap.add(9);
integerHeap.add(10);
integerHeap.remove();
integerHeap.remove();
integerHeap.remove();
integerHeap.remove();
integerHeap.remove();
integerHeap.remove();
integerHeap.remove();
integerHeap.remove();
integerHeap.remove();
integerHeap.remove();
stringHeap.add("A");
stringHeap.add("B");
stringHeap.add("C");
stringHeap.add("D");
stringHeap.add("E");
stringHeap.add("F");
stringHeap.add("G");
stringHeap.add("H");
stringHeap.add("I");
stringHeap.add("J");
stringHeap.add("K");
stringHeap.remove();
stringHeap.remove();
stringHeap.remove();
stringHeap.remove();
stringHeap.remove();
stringHeap.remove();
stringHeap.remove();
stringHeap.remove();
stringHeap.remove();
stringHeap.remove();
stringHeap.remove();
System.out.println("finished");
}
}
when I run my program I get an index out of bounds errors or more specifically.
java.lang.IndexOutOfBoundsException: Index: 15, Size: 10
at java.util.ArrayList.rangeCheck(ArrayList.java:604)
at java.util.ArrayList.get(ArrayList.java:382)
at MyHeap.reheapDown(MyHeap.java:61)
at MyHeap.reheapDown(MyHeap.java:48)
at MyHeap.reheapDown(MyHeap.java:48)
at MyHeap.reheapDown(MyHeap.java:48)
at MyHeap.remove(MyHeap.java:19)
at DriverP07.main(DriverP07.java:19)
So, I'm assuming the error is really simple to fix, but I have no idea how to fix it. Any help would be appreciated.
Re: Creating and Using a Heap. Index out of Bounds
Ok sorry guys, after immediately posting this I figured out my last else was pairing with the wrong if. Sorry about that, but I do have another question.
When i'm removing elements from my driver class and assigning it to variables like, temp = integerHeap.remove(); , I get a compiler error since you can't assign a comparable to an int. So my question is, since you can't cast it how would I retrieve the returned values.
Re: Creating and Using a Heap. Index out of Bounds
Quote:
temp = integerHeap.remove(); , I get a compiler error since you can't assign a comparable to an int.
Try
Code :
MyHeap<Integer> integerHeap = new MyHeap<Integer>();
In general your heap is a heap of something and the type should be there in the declaration so that the constructor, remove() method etc can do the right thing. (And, importantly, will be known to do the right thing by the compiler. I think code like you have should lead to the compiler complaining.)
Re: Creating and Using a Heap. Index out of Bounds
oh duh, thanks pbrock works perfectly now.
Re: Creating and Using a Heap. Index out of Bounds