1
import java.util.*;
import java.lang.Math;

public class Heap {

    private static int heapSize;
    
    public static void HeapSort(int [] A) {
        BuildHeap(A);
        for(int i=A.length-1; i>=1; i--) {
            int temp;
            temp=A[0];
            A[0]=A[i];
            A[i]=temp;
            heapSize--;
            Heapify(A,0);
        }
        
    }
    
    public static void BuildHeap(int [] A) {
        heapSize=A.length;
        for(int i=(int)(Math.floor(heapSize-1/2));i>=0;i--) {
            Heapify(A,i);
        }
    }
    
    public static void Heapify(int [] A,int i) {
        int largest=i;
        int le=2*i+1;
        int ri=2*i+2;
        if((le<=heapSize)&&(A[le]>A[i])) {
        largest=le;
        }
        else
            largest=i;
        if((ri<=heapSize)&&(A[ri]>A[largest])) {
            largest=ri;
        }
        if(largest!=i) {
            int temp=A[i];
            A[i]=A[largest];
            A[largest]=temp;
            Heapify(A,largest);
        }
    }
    public static void printArray(int [] A) {
        for(int i=0; i<A.length;i++)
            System.out.println(A[i]);
    }
}

This is the implementation to a heap sort that we were assigned in my data structures class. I am getting an ArrayIndexOutOfBoundsException error when I try to run the code, however. I have been trying to figure out how to fix this, and have been tinkering with the code a lot outside of the bounds of the pseudocode we were given to work off of. I'm not sure how to fix this. Please help.

If it helps, here is the code of the main method:

import java.util.*;

public class Test {
public static void main(String[] args) {
    Random rd=new Random();
    int [] arr1=new int[20];
    int [] arr2=new int[20];
    int [] arr3=new int[20];
    int [] arr4=new int[20];
    int [] arr5=new int[20];
    System.out.println("Before:");
    for(int i=0; i<arr1.length;i++)
        arr1[i]=rd.nextInt();
    System.out.println("Array 1:");
    Heap.printArray(arr1);
    for(int i=0; i<arr2.length;i++)
        arr2[i]=rd.nextInt();
    System.out.println("Array 2:");
    Heap.printArray(arr2);
    for(int i=0; i<arr3.length;i++)
        arr3[i]=rd.nextInt();
    System.out.println("Array 3:");
    Heap.printArray(arr3);
    for(int i=0; i<arr4.length;i++)
        arr4[i]=rd.nextInt();
    System.out.println("Array 4:");
    Heap.printArray(arr4);
    for(int i=0; i<arr5.length;i++)
        arr5[i]=rd.nextInt();
    System.out.println("Array 5:");
    Heap.printArray(arr5);
    Heap.HeapSort(arr1);
    Heap.HeapSort(arr2);
    Heap.HeapSort(arr3);
    Heap.HeapSort(arr4);
    Heap.HeapSort(arr5);
    System.out.println("After:");
    System.out.println("Array 1:");
    Heap.printArray(arr1);
    System.out.println("Array 2:");
    Heap.printArray(arr2);
    System.out.println("Array 3:");
    Heap.printArray(arr3);
    System.out.println("Array 4:");
    Heap.printArray(arr4);
    System.out.println("Array 5:");
    Heap.printArray(arr5);
}
}

Also, here is the error that pops up:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 20 out of bounds for length 20
    at Heap.Heapify(Heap.java:37)
    at Heap.BuildHeap(Heap.java:24)
    at Heap.HeapSort(Heap.java:9)
    at Test.main(Test.java:32)
Mark Rotteveel
  • 100,966
  • 191
  • 140
  • 197
Whiffed
  • 11
  • 4
  • please share the full stacktrace or tell us the line where the exception occurs ? – azro Apr 14 '22 at 11:35
  • Please provide the code of Main method, and stacktrace of exception, –  Apr 14 '22 at 11:35
  • Side note: It is a quasi-standard coding convention in Java for methods names (even static ones) to start with lower case letters, and names of classes and interfaces with uppercase letters. – Hulk Apr 14 '22 at 11:38
  • 1
    Another side note: there’s no sense in calling `Math.floor` on an `int` value. Regarding your described problem, I suggest using a debugger and going step by step through your program. – Holger Apr 14 '22 at 11:58
  • `Math.floor(heapSize-1/2)` is not doing what you think it's doing. `1/2` is an `int` value, equal to `0`. – k314159 Apr 14 '22 at 12:06
  • I would strongly suggest that you take this opportunity to learn how to use a debugger to monitor the values in variables. You are passing a 20 as the index which is out of range (0-19). Remove all the random number stuff from your test driver - create a single small array of known values and run the test with that. If it succeeds, add numbers to increase the size. I think you'll find that how you calculate the index breaks down in some cases. – vsfDawg Apr 14 '22 at 12:06

0 Answers0