三元ヒープNULLポインタ例外

Question

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がどこから来たのかわかりません、私はこれを長い間把握しようとしています...助けてください！私はあなたがこのコードを持っている...

Answer 1

それについて移動するかどうかはわかりません。i = size-1場合

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はヒープ内の最後のノードを参照しています。その後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; 
}