Ternary Heap Null Pointer Exception

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

}

When running my test method, I get this error:

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)

I am not sure where the NullPointerException came from, and I've been trying to figure this out for a long time... please help me! I'm not sure how to go about it... I am not sure where the NullPointerException came from, and I've been trying to figure this out for a long time... please help me! I'm not sure how to go about it... I am not sure where the NullPointerException came from, and I've been trying to figure this out for a long time... please help me! I'm not sure how to go about it...

Answer 1

You have this code:

if (i < size && comparator.compare(keys.get(i), keys.get(i+1)) < 0 && comparator.compare(keys.get(i), keys.get(i+2)) < 0) i++;

So what happens if i = size-1? That is, i is referencing the last node in the heap. Then keys.get(i+1) is going to return null (or perhaps crash because you're trying to index beyond the end of the list).

To do this correctly, you need to check that each of the indexes is in range before you try to get and compare items.

What you're doing is checking to see if the key at index k is smaller than all of its children. So first you want to find the smallest child. The way I've done this in the past is:

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