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)