I'm trying to do a fibonacci heap, and I don't understand why I get an "indexofboundsException" error in the consolidate method, I implement it just like geek_for_geeks, although it is in C language, I am doing it in java, and it should work :(.
As I was saying, I am trying to do the implementation to eliminate the minimum of fibonacci heap, the insertion was successful, the display also, but the consolidate, I get an error in the array:
float temp2 = (float) ((Math.log(nro_nodos)) / (Math.log(2)));
int temp3 = (int)temp2;
Nodo[] arr = new Nodo[temp3];
for (int i = 0; i <= temp3; i++)
arr[i] = null;
IndexodboundsException says to me, so far, I have implemented it just as the geekforgeeks page says, but maybe it finds different things to do in java, in C it says:
int temp1;
float temp2 = (log(no_of_nodes)) / (log(2));
int temp3 = temp2;
struct node* arr[temp3];
for (int i = 0; i <= temp3; i++)
arr[i] = NULL;
My class Nodo is :
package Fibonacci_Heap;
public class Nodo {
Nodo<T> parent;
Nodo<T> child;
Nodo<T> left;
Nodo<T> right;
T dato;
int degree = 0;
public Nodo(T dato){
this.dato = dato;
}
} And my class FH(fibonacci heap):
package Fibonacci_Heap; public class FH {
int nro_nodos = 0;
Nodo<T> min = null;
void Fibonnaci_link(Nodo<T> ptr2, Nodo<T> ptr1)
{
(ptr2.left).right = ptr2.right;
ptr2.right.left = ptr2.left;
if (ptr1.right == ptr1)
min = ptr1;
ptr2.left = ptr2;
ptr2.right = ptr2;
ptr2.parent = ptr1;
if (ptr1.child == null)
ptr1.child = ptr2;
ptr2.right = ptr1.child;
ptr2.left = ptr1.child.left;
((ptr1.child).left).right = ptr2;
(ptr1.child).left = ptr2;
if (ptr2.dato.compareTo(ptr1.child.dato) < 0)
ptr1.child = ptr2;
ptr1.degree++;
}
public void consolidar(){
int temp1;
float temp2 = (float) ((Math.log(nro_nodos)) / (Math.log(2)));
int temp3 = (int)temp2;
Nodo[] arr = new Nodo[temp3];
for (int i = 0; i <= temp3; i++)
arr[i] = null;
Nodo ptr1 = min;
Nodo ptr2;
Nodo ptr3;
Nodo ptr4 = ptr1;
do{
ptr4 = ptr4.right;
temp1 = ptr1.degree;
while(arr[temp1] != null){
ptr2 = arr[temp1];
if(((Comparable) ptr1.dato).compareTo(ptr2.dato) > 0){
ptr3 = ptr1;
ptr1 = ptr2;
ptr2 = ptr3;
}
if(ptr2 == min){
min = ptr1;
}
Fibonnaci_link(ptr2, ptr1);
if (ptr1.right == ptr1)
min = ptr1;
arr[temp1] = null;
temp1++;
}
arr[temp1] = ptr1;
ptr1 = ptr1.right;
}while(ptr1 != min);
min = null;
for (int j = 0; j <= temp3; j++) {
if (arr[j] != null) {
arr[j].left = arr[j];
arr[j].right = arr[j];
if (min != null) {
(min.left).right = arr[j];
arr[j].right = min;
arr[j].left = min.left;
min.left = arr[j];
if (((Comparable) arr[j].dato).compareTo(min.dato) < 0 )
min = arr[j];
}
else {
min = arr[j];
}
if (min == null)
min = arr[j];
else if (((Comparable) arr[j].dato).compareTo(min.dato) < 0)
min = arr[j];
}
}
}
void eliminar_min()
{
if (min == null)
throw new RuntimeException("el arbol esta vacio");
else {
Nodo temp = min;
Nodo pntr;
pntr = temp;
Nodo x = null;
if (temp.child != null) {
x = temp.child;
do {
pntr = x.right;
(min.left).right = x;
x.right = min;
x.left = min.left;
min.left = x;
if (((Comparable) x.dato).compareTo(min.dato) < 0)
min = x;
x.parent = null;
x = pntr;
} while (pntr != temp.child);
}
(temp.left).right = temp.right;
(temp.right).left = temp.left;
min = temp.right;
if (temp == temp.right && temp.child == null)
min = null;
else {
min = temp.right;
consolidar();
}
nro_nodos--;
}
}
void display()
{
Nodo ptr = min;
if (ptr == null)
System.out.print("esta vacio");
else {
System.out.println("los nodos raiz son: ");
do {
System.out.print(ptr.dato);
ptr = ptr.right;
if (ptr != min) {
System.out.print("-->");
}
} while (ptr != min && ptr.right != null);
System.out.println();
System.out.print("El nuemro de nodos es "+nro_nodos+" nodos");
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
FH<Integer> heap = new FH();
heap.insercion(5);
heap.insercion(2);
heap.insercion(8);
heap.display();
heap.eliminar_min();
}
}
The exception stacktrace looks like this:
los nodos raiz son: 2-->5-->8 El nuemro de nodos es 3 nodosException in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1 at Fibonacci_Heap.FH.consolidar(FH.java:56) at Fibonacci_Heap.FH.eliminar_min(FH.java:138) at Fibonacci_Heap.FH.main(FH.java:173)
There is an error in the original C code that you’re repeating in Java. Specifically, look at your adapted Java code:
Nodo[] arr = new Nodo[temp3];
for (int i = 0; i <= temp3; i++)
arr[i] = null;
This creates an array of size temp3, whose indices range from 0 to temp3 - 1, respectively. But in the next loop, you’re iterating up to and including index temp3, which walks off the end of the array.
Given the C code you shared above, it looks like this same error is present in the C code as well. A difference between Java and C is that bad writes in C lead to undefined behavior and can fail silently, compared with Java where these writes trigger exceptions.
Based on my understanding of Fibonacci heaps, I think you should allocate an array whose size is temp3 + 1 here. That would fix your indexing issue.
Another concern here: due to rounding errors, Math.log(nro_nodos) / Math.log(2), casted to an integer, may not actually give you log2 n. Consider using Math.round here to avoid this.
Also, a shameless self-plug: many years back I coded up a Java version of a Fibonacci heap that uses a slightly different strategy when doing the consolidate step. Also, for more background on how consolidation works, check out these slides on lazy binomial heaps, which gives another view of what the consolidation step does.
Hope this helps!