java中fibonacci堆的consolidate方法的实现，一个IndexofBoundsException的错误

Question

我正在尝试做一个斐波那契堆，我不明白为什么我在合并方法中得到一个“indexofboundsException”错误，我实现它就像 geek_for_geeks，虽然它是在 C 中语言，我在 java 中进行，它应该可以工作 :(.

正如我所说，我正在尝试执行消除斐波那契堆的最小值，插入成功，显示也一样，但是合并，我在数组中出现错误：

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 对我说，到目前为止，我已经按照 geekforgeeks 页面所说的那样实现了它，但也许它在 java 中发现了不同的事情要做，在 C 中它说：

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;

我的 class 诺多是：

package Fibonacci_Heap;

public class 诺多{

Nodo<T> parent;
Nodo<T> child;
Nodo<T> left;
Nodo<T> right;
T dato;
int degree = 0;
public Nodo(T dato){
    this.dato = dato;
}

} 还有我的 class FH（斐波那契堆）：

包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();
}

}

enter image description here

异常堆栈跟踪如下所示：

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)

Answer 1

您在 Java 中重复的原始 C 代码中存在错误。具体看你改编的Java代码：

Nodo[] arr = new Nodo[temp3];
for (int i = 0; i <= temp3; i++) 
    arr[i] = null;

这将创建一个大小为 temp3 的数组，其索引范围分别为 0 到 temp3 - 1。但在下一个循环中，您将迭代到并包括索引 temp3，它离开数组的末尾。

鉴于您在上面共享的 C 代码，C 代码中似乎也存在同样的错误。 Java 和 C 之间的区别在于，C 中的错误写入会导致 未定义的行为 并且可以无提示地失败，而 Java 这些写入会触发异常。

根据我对斐波那契堆的理解，我认为你应该在这里分配一个大小为temp3 + 1的数组。这将解决您的索引问题。

这里还有一个问题：由于舍入错误，Math.log(nro_nodos) / Math.log(2) 转换为整数后，实际上可能不会给您 log₂ n。考虑在这里使用 Math.round 来避免这种情况。

另外，一个无耻的自我插件：很多年前我编码了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，这给出了巩固步骤的另一种观点。

希望对您有所帮助！

java中fibonacci堆的consolidate方法的实现，一个IndexofBoundsException的错误

Implementation of the consolidate method of fibonacci heap in java, an error of IndexofBoundsException

java

data-structures

fibonacci-heap