im a biginner to practice building up a Heap. But when I run it in a Terminal it will have an Exception. The following code is this:
import java.util.Arrays;
import java.util.Scanner;
class B4A1 {
public static void swap(int[] data, int i, int j) {
int h = data[i];
data[i] = data[j];
data[j] = h;
}
public static int left(int i) {
return 2*i;
}
public static int right(int i) {
return 2*i + 1;
}
public static int parent(int i) {
return i/2;
}
public static void maxHeapifyUp(int[] data, int i) {
/**********************************************************/
int temp = data[i];
while(i>=0 && data[i] > data[parent(i)]) {
data[i] = data[parent(i)];
i = parent(i);
}
data[i] = temp;
}
/**********************************************************/
}
public static void maxHeapifyDown(int[] data, int i, int n) {
/**********************************************************/
int l = left(i);
int r = right(i);
int largest;
if(l<=(n-1) && data[l]>data[i]) {
largest = l;
}else {
largest = i;
}
if(r<=(n-1) && data[r]>data[largest]) {
largest = r;
}
if(largest != i) {
swap(data, i, largest);
maxHeapifyDown(data, largest, n);
}
/**********************************************************/
}
public static void buildMaxHeap(int[] data) {
/**********************************************************/
for(int i = (data.length/2); i > 0; i--) {
maxHeapifyUp(data, i);
}
/**********************************************************/
}
public static int extractMax(int[] data, int n) {
/**********************************************************/
assert n > 0;
int max = data[0];
data[0] = data[n-1];
n--;
maxHeapifyDown(data, 0, n);
/**********************************************************/
return 0;
}
public static int heapSelect(int[] data, int k) {
/**********************************************************/
buildMaxHeap(data);
int n = data.length;
while(k > 0) {
extractMax(data, n);
k--;
}
return data[n-k];
/**********************************************************/
}
public static void main(String[] args) {
int k = Integer.parseInt(args[0]);
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = input.nextInt();
}
input.close();
System.out.print("Input Array: ");
System.out.println(Arrays.toString(arr));
int v = heapSelect(arr, k);
System.out.println("The " + k + "-biggest element is " + v);
}
}
the error looks like this
java B4A1 3
5 1 2 2 3 4
Input Array: [1, 2, 2, 3, 4]
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 5
at B4A1.maxHeapifyUp(B4A1.java:24)
at B4A1.maxHeapifyUp(B4A1.java:27)
at B4A1.maxHeapifyUp(B4A1.java:27)
at B4A1.maxHeapifyUp(B4A1.java:27)
at B4A1.buildMaxHeap(B4A1.java:57)
at B4A1.heapSelect(B4A1.java:75)
at B4A1.main(B4A1.java:100)
i tried to see if it is wrong setting bounderys for n and i, but cannot find anything that would be wrong.
Would be very thankful if someone could help me