ここで質問するのは初めてです。正式な手順を破らないように最善を尽くします。
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);
}
}