This is my first time asking a question on here, and I'll do my best not to break any formal procedures.
I'm trying to implement a small (and generic) D-ary heap ( http://en.wikipedia.org/wiki/D-ary_heap ) in Java, with the help of Mark Allen Weiss binary heap-code (http://users.cis.fiu.edu/~weiss/dsaajava2/code/BinaryHeap.java) and the code is almost done. However, there seems to be a problem when testing the heap; the test case goes into an infinte loop and I don't know why. I'd really appreciate help with resolving the issue.
Here's the relevant part of the test case ("heap" is a 3-heap):
@Test
public void testFindMin() {
insert(3, 4, 6, 7, 1, 8, 2, 5);
assertTrue(heap.size() == 8);
a开发者_如何转开发ssertTrue(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);
}
And here's my code:
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);
}
}
I think that the bug is in this code:
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;
}
Notice that in this loop, you only change the value of child
in the nested for
loop, but never elsewhere. This means that if on some particular iteration none of the child nodes of the current node are less than the element at index child
, then child
is never reassigned and when you execute the loop step condition hole = child
nothing will happen. It seems like if you got unlucky with your heap structure this could easily be causing your infinite loop.
Similarly, in this loop you're never reassigning tempChild
, so on each iteration tempChild
will pick up where it left off on the previous iteration. If on one of those iterations tempChild
was equal to size
, then the inner loop will never execute and each loop iteration will have no effect, again causing the infinite loop.
To fix this, I think you want to recompute tempChild
and index
on each iteration, as shown here:
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;
}
I'm not sure if this is correct because I can't test it without access to the base class, but this seems like it's probably the culprit. Try it out and let me know how it works.
精彩评论