在实现Heapify删除MinHeap中的最小值时，空指针异常

Question

对于下面的程序:

public class MinHeap<T extends Comparable<? super T>>
implements HeapInterface<T> {
private T[] backingArray;
private int size;
// Do not add any more instance variables
/**
 * Creates a Heap.
 */
public MinHeap() {
    backingArray = (T[]) new Comparable[STARTING_SIZE];
    size = 0;
}
@Override
public void add(T item) {
    if (item == null) {
        throw new IllegalArgumentException("Item was null.");
    }
    if (size + 1 >= backingArray.length) {
        resize();
    }
    backingArray[size + 1] = item;
    int i = size + 1;
    while (i > 1 && backingArray[i].compareTo(backingArray[i / 2]) <= 0) {
        swap(backingArray[i], backingArray[i / 2], i, i / 2);
        i = i / 2;
    }
    size++;
}
private void resize() {
    T[] backingArrayTemp = backingArray;
    backingArray = (T[]) new Comparable[backingArrayTemp.length * 2];
    for (int i = 1; i < size + 1; i++) {
        backingArray[i] = backingArrayTemp[i];
    }
}
private void swap(T item1, T item2, int i, int parent) {
   backingArray[parent] = item1;
   backingArray[i] = item2;
}
@Override
public T remove() {
    if (isEmpty()) {
        throw new NoSuchElementException("Heap is empty.");
    }
    T temp = backingArray[1];
    backingArray[1] = backingArray[size + 1];
    size--;
    heapify(1);
    return temp;
}
private void heapify(int i) {
    int left = 2*i;
    int right = 2*i + 1;
    int min = i;
    if (left < size && backingArray[left].compareTo(backingArray[min])
            < 0) {
        min = left;
    }
    if (right < size
            && backingArray[right].compareTo(backingArray[min]) < 0) {
        min = right;
    }
    if (min != i) {
        swap(backingArray[i], backingArray[min], i, min);
        heapify(min);
    }
}
@Override
public boolean isEmpty() {
    return size == 0;
}
@Override
public int size() {
    return size;
}
@Override
public void clear() {
    size = 0;
    backingArray = (T[]) new Comparable[STARTING_SIZE];
}

从i = 1开始索引。我的添加方法工作得很好，我试过从backingArray[1] = backingArray[size + 1];到backingArray[1] = backingArray[size]在remove方法中，但这似乎不对，也不起作用。它去掉了空指针，但没有通过我所有的测试。在

处得到空指针

backingArray[left].compareTo(backingArray[min]) < 0)

因为backingArray[min]是空的。

堆栈跟踪

java.lang.NullPointerException
at java.lang.Integer.compareTo(Integer.java:1216)
at java.lang.Integer.compareTo(Integer.java:52)
at MinHeap.heapify(MinHeap.java:68)
at MinHeap.remove(MinHeap.java:60)

Answer 1

我不能真正测试这个，现在，但我认为主要问题是在resize()方法。当您创建保存数据

的临时数组时

T[] backingArrayTemp = backingArray;

实际上告诉新数组指向内存中与原始backingArray相同的地址。然后重新分配backingArray和temp数组，因为它们指向内存中的相同位置。那么，当然，所有的元素都不会被初始化，并且行为也不会像预期的那样。

正确的方法是创建一个"new"数组，然后复制这些值:

T[] backingArrayTemp = new T[backingArray.length];
for(int i = 0; i < backingArray.length; ++i)
    backingArrayTemp[i] = new T(backingArray[i]);

其中每个元素都用构造函数复制，以避免类似问题。

About heapify() -我不知道你将如何使用最小堆，但我猜你总是一次放一个元素。如果需要从随机数组创建堆，则需要一个更复杂的例程来遍历整个堆。如果您有兴趣的话，我可以为您提供更多的信息。

Answer 2

问题是我没有设置backingArray[size] = null。