0

Very basic question but I am quite stuck and growing desperate. Any helpful advice would be very sincerely appreciated. Thanks

I'm attempting to add node elements from an existing ArrayList into a new empty ArrayList one at a time and then calling heap methods on the new ArrayList. The idea is to call the heap methods on a list of 1 element, then on a list of 2 elements, then on a list of 3 elements, etc. However, when attempting to call my initial 'Build_min_Heap()' method, I am getting the following exception: java.lang.IndexOutOfBoundsException: Index: 3, Size: 3

My Heap class is as follows:

import java.util.*;

public class Heap 
{
int heapSize;
Graph gr;

//constructor for heap object with the following attributes:
//a graph object and an int representing the size of an arraylist of nodes
public Heap(ArrayList<Node> A, Graph g)
{
    heapSize = A.size();
    gr = g;
}

public int getHeapSize() {
    return heapSize;
}

public void setHeapSize(int heapSize) {
    this.heapSize = heapSize;
}

//heap methods

public int Parent(ArrayList<Node> A, int i)
{
    //if (i == 1)
        //return (Integer)null;

    if (i%2 != 0)
        return i/2;

    else 
        return (i-1)/2;
}

public int Left(ArrayList<Node> A, int i)
{
    //if (2*i < heapSize)
        return (2*i)+1;
    //else
        //return (Integer)null;
}

public int Right(ArrayList<Node> A, int i)
{
    //if ((2*i)+1 < heapSize)
        return 2*i+2;
    //else
        //return (Integer)null;
}

public void Heapify(ArrayList<Node> A, int i)
{
    Node smallest;
    Node temp;
    int index;

    int l = Left(A,i);
    int r = Right(A,i);

    //if (l <= heapSize-1 && Integer.parseInt(A.get(l).getVal()) < Integer.parseInt(A.get(i).getVal()))
    if (Integer.parseInt(A.get(l).getVal()) < Integer.parseInt(A.get(i).getVal()))
    {   
        //left child is smaller
        smallest = A.get(l);
        index = l;
    }   
    else
    {   
        //parent node is smaller
        smallest = A.get(i);
        index = i;
    }   

    //if (r <= heapSize-1 && Integer.parseInt(A.get(r).getVal()) < Integer.parseInt(smallest.getVal()))
    if (Integer.parseInt(A.get(r).getVal()) < Integer.parseInt(smallest.getVal()))
    {   
        //right child is smaller
        smallest = A.get(r);
        index = r;
    }

    if (index != i)
    {   
        //if the smallest element is not the parent node
        //swap the smallest child with the parent  
        temp = A.get(i);
        A.set(i, A.get(index));
        A.set(index, temp);

        //recursively call heapify method to check next parent/child relationship
        Heapify(A, index);
    }   
}

//method to construct min heap from unordered arraylist of nodes
public void Build_min_Heap(ArrayList<Node> A)
{
    int i;
    int heapSize = A.size();

    for (i = (heapSize/2); i>=0; i--)
    {   
        Heapify(A, i);
        System.out.print(gr.toString2()+"\n");
    }   

//method to sort in descending order, a min heap
public void heap_Sort(ArrayList<Node> A)
{
    Node temp;

    Build_min_Heap(A);
    //System.out.println(gr.toString2()+"\n");

    for(int i = A.size()-1; i >= 1; i--)
    //for (int i = 0; i <= A.size()-1; i++)
    {
        //exchange a[0] with a[i]
        temp = A.get(0);
        A.set(0, A.get(i));
        A.set(i, temp);

        //temp = A.get(A.size()-1);
        //A.set(A.size()-1, A.get(i));
        //A.set(i, temp);

        //decrement heapSize
        heapSize--;

        //recursive heapify call
        Heapify(A, 0);
    }
}

the class containing the main method is very long but the significant portion is this:

    g = new Graph();
    readGraphInfo( g );
    h = new Heap(g.getNodeList(), g);
    DelivB dB = new DelivB(inputFile, g);


    int numElements = g.getNodeList().size();
    ArrayList<Node> ordered_nodeList = new ArrayList<Node>(15);


        for (int i = 0; i <= numElements; i++)
        {
            ordered_nodeList.add(i, g.getNodeList().get(i));

            h.Build_min_Heap(ordered_nodeList);
        }
Hovercraft Full Of Eels
  • 283,665
  • 25
  • 256
  • 373
Trixie the Cat
  • 317
  • 3
  • 18
  • You may not like my solution but I have to give it regardless: best to run this through the debugger of your IDE of choice to study the state of the variables of your objects just before and when the exception occurs. You already have a huge clue -- the stacktrace -- which tells you exactly where and when the exception is occurring, and the values of the array or collection index when the exception occurs. – Hovercraft Full Of Eels Sep 25 '18 at 22:11
  • Of concern, your question seems to be missing key information, such as the line that is throwing the collection, the array or collection that is involved, why it's using an index of 3 when its size is only 3,.... this is all *key* information that your stacktrace is giving you, but that you have not yet shared with us. – Hovercraft Full Of Eels Sep 25 '18 at 22:16
  • @HovercraftFullOfEels thank you for attempting to help. The exception is thrown at the very first 'if' statement of my 'Heapify' method. The reason the size is 3 is because I'm attempting to copy an ArrayList of 3 elements, one element at a time into a empty ArrayList and then calling the 'build_min_heap' after each element is added, so trying to copy 1 element then call the method on the list of 1 element then copy the 2nd element and calling the method on the 2 element list, etc. – Trixie the Cat Sep 25 '18 at 22:24
  • But you know that arrays and ArrayLists are 0-based, and so an ArrayList or array of size 3, has indices that can go from 0 to 2, and in your code somewhere, somehow (only you can test at this point), you're trying to use an index of 3, which will (*and should*) cause an index out of bounds exception. – Hovercraft Full Of Eels Sep 25 '18 at 22:26
  • @HovercraftFullOfEels again thank you. I believe it has to do with the math programmed into my heap methods. If I call the heap methods on a full list it works well, but when calling methods on a heap of one element, it causes a problem since my Heapify method immediately assigns a right and left child. I think the issue is obviously, if you only have one element and no children the heapify method needs to account for that. I am attempting to rework it now to account for the trivial cases of little to no elements in the heap – Trixie the Cat Sep 25 '18 at 22:48

0 Answers0