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

Question

这是我第一次在这里提问，我会尽力不违反任何正式程序。

我正在尝试实现一个小型（通用）D 元堆（ http://en. wikipedia.org/wiki/D-ary_heap ）在 Java 中，在 Mark Allen Weiss 二进制堆代码 (http://users.cis.fiu.edu/~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

我认为 bug 出在这段代码中：

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;
}

请注意，在这个循环中，您只更改嵌套 for 循环中 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;
}

我不确定这是否正确，因为我无法测试它无法访问基类，但这似乎可能是罪魁祸首。尝试一下并让我知道它是如何工作的。