三元堆空指针异常

问题描述:

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; 
}