Hey guys, I'm currently trying to build and use a heap so I created the two following classes.
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); } } } }
when I run my program I get an index out of bounds errors or more specifically.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"); } }
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.