Java D堆实现 - deleteMin中的无限循环

Question

这是我第一次在这里问一个问题，我会尽我所能不要打破任何正式的程序。

我试图在Mark Allen Weiss二进制堆代码（http://users.cis.fiu.edu/）的帮助下在Java中实现一个小的（通用的）D-ary堆（http://en.wikipedia.org/wiki/D-ary_heap） 〜weiss/dsaajava2/code/BinaryHeap.java），代码几乎完成。但是，测试堆时似乎有问题;测试用例进入无限循环，我不知道为什么。我真的很感谢帮助解决这个问题。

下面是测试案例的相关部分（“堆”是一个3堆）：

@Test 
public void testFindMin() { 
    insert(3, 4, 6, 7, 1, 8, 2, 5); 
    assertTrue(heap.size() == 8); 
    assertTrue(heap.findMin() == 1); 

    heap.makeEmpty(); 
    assertTrue(heap.isEmpty()); 

    insert(182, 64, 233, 906, 42, 678); 
    assertTrue(heap.size() == 6); 
    assertTrue(heap.findMin() == 42); 

    heap.printHeap(); //The heap is 42, 64, 233, 906, 182, 678 

    assertTrue(heap.deleteMin() == 42); //Here's where it gets stuck 
    assertTrue(heap.size() == 5); 
    assertTrue(heap.findMin() == 64); 
} 

这里是我的代码：

public class MyMiniHeap<T extends Comparable<? super T>> implements MiniHeap<T> { 

private int heapSize = 0; 
private T[] heapArray; 
private static final int DEFCAP = 10; 
private int d; 

public MyMiniHeap() { 
    this(2, DEFCAP); 
} 

public MyMiniHeap(int children) { 
    this(children, DEFCAP); 
} 

@SuppressWarnings("unchecked") 
public MyMiniHeap(int children, int capacity) { 
    heapSize = 0; 
    d = children; 
    heapArray = (T[]) new Comparable[capacity + 1]; 
} 


/** 
* Inserts an element into the heap, placing it correctly according 
* to heap properties. 
* 
* @param element the element to insert. 
* @throws IllegalArgumentException if the element to insert is null. 
*/ 
public void insert(T element) { 
    if (element == null) 
     throw new IllegalArgumentException("cannot insert null"); 

    if (size() == heapArray.length - 1) 
     doubleArraySize(); 

    int hole = ++heapSize; 
    for(; hole > 1 && element.compareTo(heapArray[getParent(hole)]) < 0; hole = getParent(hole)) { 
     heapArray[hole] = heapArray[getParent(hole)]; 
    } 
    heapArray[hole] = element; 
} 

/** 
* Deletes the smallest element in the heap. 
* 
* @return the smallest element in the heap. 
* @throws IllegalStateException if the heap is empty. 
*/ 
public T deleteMin() { 
    if (isEmpty()) 
     throw new IllegalStateException("Error: Empty heap"); 

    T minItem = findMin(); 
    heapArray[1] = heapArray[heapSize--]; 
    percolateDown(1); 

    return minItem; 
} 

/** 
* Checks if the heap is empty or not. 
* 
* @return true if the heap is empty, otherwise false. 
*/ 
public T findMin() { 
    if (isEmpty()) 
     throw new IllegalStateException("Error: Empty heap"); 

    return heapArray[1]; 
} 

private void percolateDown(int hole) { 
    int child = getChild(hole); 
    int tempChild = getChild(hole); 
    T tempElement = heapArray[hole]; 

    for(; getChild(hole) <= size(); hole = child) { 
     for(int i = 0; i < d && tempChild != size(); i++, tempChild++){ 
      if(heapArray[tempChild + 1].compareTo(heapArray[child]) < 0){ 
       child = tempChild + 1; 
      } 
     } 

     if (heapArray[child].compareTo(tempElement) < 0) 
      heapArray[hole] = heapArray[child]; 
     else 
      break; 
    } 
    heapArray[hole] = tempElement; 
} 

@SuppressWarnings("unchecked") 
private void doubleArraySize() { 
    T [] old = heapArray; 
    heapArray = (T [])new Comparable[old.length * 2]; 
    for (int i = 0; i < old.length; i++) 
     heapArray[i] = old[i]; 
} 

public boolean isEmpty() { 
    return size() == 0; 
} 

public void makeEmpty() {  
    heapSize = 0; 
} 

public int size() { 
    return heapSize; 
} 

/** 
* Finds the index of the first child for a given parent's index. 
* This method is normally private, but is used to test the 
* correctness of the heap. 
* 
* @param parent the index of the parent. 
* @return an integer with the index of the parent's first child. 
*/ 
public int getChild(int parent) { 
    return d * (parent - 1) + 2; 
} 

/** 
* Finds the index of a parent for a given child's index. 
* This method is normally private, but is used to test 
* the correctness of the heap. 
* 
* @param child the index of the child. 
* @return an integer with the child's parent's index. 
*/ 
public int getParent(int child) { 
    return (child - 2)/d + 1; 
} 

public void printHeap() { 
    String output = ""; 
    for (int i = 1; i <= size(); i++) 
     output += heapArray[i].toString() + " "; 
    System.out.println(output); 
} 
} 

Answer 1

我认为错误是在这代码：

for(; getChild(hole) <= size(); hole = child) { 
    for(int i = 0; i < d && tempChild != size(); i++, tempChild++){ 
     if(heapArray[tempChild + 1].compareTo(heapArray[child]) < 0){ 
      child = tempChild + 1; 
     } 
    } 

    if (heapArray[child].compareTo(tempElement) < 0) 
     heapArray[hole] = heapArray[child]; 
    else 
     break; 
} 

注意，在这个循环中，你只能改变嵌套的child值循环，但从来没有其他地方。这意味着如果在某个特定的迭代中当前节点的子节点都没有小于索引child中的元素，那么child永远不会被重新分配，并且当您执行循环步骤条件hole = child时不会发生任何事情。看起来如果你的堆结构不幸运，这很容易导致你的无限循环。

同样，在这个循环中，你永远不会重新分配tempChild，所以在每次迭代中，tempChild都会在上次迭代中停止的地方。如果在其中一个迭代中tempChild等于size，那么内部循环将永远不会执行，并且每个循环迭代都将不起作用，从而导致无限循环。

为了解决这个问题，我想你想重新计算在每次迭代tempChild和index，如下所示：

for(; getChild(hole) <= size(); hole = child) { 
    child = getChild(hole); 
    int tempChild = getChild(hole); 

    for(int i = 0; i < d && tempChild != size(); i++, tempChild++){ 
     if(heapArray[tempChild + 1].compareTo(heapArray[child]) < 0){ 
      child = tempChild + 1; 
     } 
    } 

    if (heapArray[child].compareTo(tempElement) < 0) 
     heapArray[hole] = heapArray[child]; 
    else 
     break; 
} 

我不知道这是否是正确的，因为我不能没有访问测试到基类，但这似乎可能是罪魁祸首。试试看，让我知道它是如何工作的。