Реализация Java-кучи - бесконечный цикл в deleteMin ()

Question

Я впервые задаю здесь вопрос, и постараюсь не нарушать никаких формальных процедур.

Я пытаюсь реализовать небольшую (и общую) кучу D-ар (http://en.wikipedia.org/wiki/D-ary_heap) в Java с помощью двоичного кода кучи Марка Аллена Вейса (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

Я думаю, что ошибка в этом коде:

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, но никогда в другом месте. Это означает, что если на какой-то конкретной итерации ни один из дочерних узлов текущего узла не меньше, чем элемент с индексом 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;
}

Я не уверен, что это правильно, потому что я не могу проверить это без доступа к базовому классу, но, похоже, это виновник. Попробуйте и дайте мне знать, как это работает.