3

这是我第一次在这里提问，我会尽量不破坏任何正式程序。

我正在尝试在 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);
}
}
4

1 回答 1

4

我认为该错误在此代码中：

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嵌套for循环中的值，而不会更改其他地方的值。这意味着，如果在某个特定的迭代中，当前节点的所有子节点都不小于 index 处的元素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;
}

我不确定这是否正确，因为如果不访问基类就无法对其进行测试，但这似乎是罪魁祸首。试试看，让我知道它是如何工作的。

于 2011-02-12T22:42:27.510 回答