三元堆空指针异常
问题描述:
package queue;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class TernaryHeap <T extends Comparable<T>> extends
AbstractPriorityQueue<T>
{
private List<T> keys;
private int size;
public TernaryHeap()
{
this(Comparator.naturalOrder());
}
public TernaryHeap(Comparator<T> comparator)
{
super(comparator);
keys = new ArrayList<>();
keys.add(null);
size=0;
}
@Override
public int size() {return size;}
@Override
public void add(T key)
{
keys.add(key);
swim(++size);
}
@Override
protected T removeAux()
{
Collections.swap(keys, 1, size);
T max = keys.remove(size--);
sink(1);
return max;
}
private void swim(int k) // intended to identify parent method and swap if child is bigger than parent
{
while (1 < k && comparator.compare(keys.get((k-1)/3), keys.get(k)) < 0)
{
Collections.swap(keys, (k-1)/3, k);
k -= 1; k /= 3;
}
}
private void sink(int k) // not sure if I got this right... intended to compare keys with 2 other children
{
for (int i=k*3; i<=size; k=i,i*=3)
{
if (i < size && comparator.compare(keys.get(i), keys.get(i+1)) < 0 && comparator.compare(keys.get(i), keys.get(i+2)) < 0) i++;
if (comparator.compare(keys.get(k), keys.get(i)) >= 0) {
break;
}
Collections.swap(keys, k, i);
}
}
运行我的检验方法,我得到这个错误:
java.lang.NullPointerException
at
java.util.Comparators$NaturalOrderComparator.compare(Comparators.java:52)
at java.util.Comparators$NaturalOrderComparator.compare(Comparators.java:47)
at queue.TernaryHeap.swim(TernaryHeap.java:47)
at queue.TernaryHeap.add(TernaryHeap.java:33)
我不知道其中的NullPointerException是从哪里来的,我一直在努力弄清楚了很长一段时间...请帮助我!我不知道如何去... 我不知道NullPointerException来自哪里,我一直试图找出很长一段时间...请帮助我!我不知道如何去... 我不知道NullPointerException来自哪里,我一直试图找出很长一段时间...请帮助我!我不知道如何去了解它...
答
你有这样的代码:
if (i < size && comparator.compare(keys.get(i), keys.get(i+1)) < 0 && comparator.compare(keys.get(i), keys.get(i+2)) < 0) i++;
所以,如果i = size-1
会发生什么?也就是说,i
正在引用堆中的最后一个节点。然后keys.get(i+1)
将返回null
(或者可能因为您尝试索引超出列表的末尾而崩溃)。
要正确执行此操作,需要在尝试获取和比较项目之前检查每个索引是否在范围内。
你正在做的是检查索引k
的密钥是否小于其所有子级。所以首先你想找到最小的孩子。我过去的做法是:
int smallestChild = i;
if (i < size-1 && comparator.compare(keys.get(smallestChild), keys.get(i+1)) < 0)
{
++smallestChild;
}
if (i < size-2 && comparator.compare(keys.get(smallestChild), keys.get(i+2)) < 0)
{
++smallestChild;
}
// Then compare the key at `k` with the smallest child:
if (comparator.compare(keys.get(k), keys.get(smallestChild) >= 0)
{
break;
}