Почему я получаю нулевое значение в строке, которая сравнивает два индекса в моей куче очереди с приоритетами? - PullRequest
Новая
       76

Почему я получаю нулевое значение в строке, которая сравнивает два индекса в моей куче очереди с приоритетами?

0 голосов
/ 27 ноября 2018

Я делаю кучу очередей с приоритетом типа T. Когда я добавляю более одного целого числа в свою кучу, я получаю исключение нулевого указателя на строке 55 , где метод reheapUp использует компараторрешить, какое целое число получает приоритет.Я застрял на этом в течение нескольких часов.Сначала я подумал, что должен был реализовать общий метод сравнения, но это не имеет смысла, потому что не было бы ничего достаточно конкретного для сравнения.Я использую метод сравнения из старого проекта, в котором я создал карту дерева двоичного поиска, в которой сравнивались строки.

/*
* PQHeap.java
* 11/12/18
*/

import java.util.Comparator;
import java.util.*;

public class PQHeap<T>{
    private Object[] heap; //hash table
    private int heapSize;
    private int capacity;
    private Comparator<T> comparator;

    public PQHeap(Comparator<T> comparator){
        heapSize = 0;
        capacity = 100;
        heap = new Object[capacity];
    }


    public int size(){
        return this.heapSize;
    }

    public void add(T obj){

        ensureCapacity();
        //add to lower right most leaf
        heap[heapSize++] = obj;
        reheapUp();

    }



    public void ensureCapacity(){
        if(heapSize < heap.length/2)
            return;
        Object newHeap[] = new Object[2*heap.length];

        for(int i=0; i<heap.length; i++)
            newHeap[i] = heap[i];
        heap = newHeap;
    }

    @SuppressWarnings("unchecked")
    private void reheapUp(){

        int outOfPlaceInd = heapSize - 1;
        while(outOfPlaceInd > 0){
            int parentInd = (outOfPlaceInd - 1)/2;
            **if (comparator.compare((T)heap[outOfPlaceInd], (T)heap[parentInd]) < 0)**
            {
                swap(outOfPlaceInd, parentInd);
                outOfPlaceInd = (outOfPlaceInd-1)/2;
            }
            else{
                return;
            }
        }
    }

    private void swap(int i, int j){
        Object copy = heap[i];
        heap[i] = heap[j];
        heap[j] = copy;
    }

    @SuppressWarnings("unchecked")
    public T remove(){
        if(heapSize == 0)
            throw new IllegalStateException("Trying to remove from an empty PQ!");
        Object p = heap[0];
        heap[0] = heap[--heapSize];
        reheapDown();
        return (T)p;
    }


    @SuppressWarnings("unchecked")
    private void reheapDown(){
        int outOfPlaceInd = 0;
        int leftInd = 2*outOfPlaceInd+1; //left child
        int rightInd = 2*outOfPlaceInd+2; //right child

        while(leftInd <= heapSize-1){
            int smallerChildInd = leftInd;

            if ((rightInd < heapSize) && (comparator.compare((T)heap[rightInd], (T)heap[leftInd]) < 0))
                smallerChildInd = rightInd;
                // is the parent smaller or equal to the smaller child
            int compare = comparator.compare((T)heap[outOfPlaceInd], (T)heap[smallerChildInd]);
                // if the parent is larger than the child...swap with smaller child
            if (compare > 0)
            {
                swap(outOfPlaceInd, smallerChildInd);

                // update indices
                outOfPlaceInd = smallerChildInd;
                leftInd = 2*outOfPlaceInd + 1;
                rightInd = 2*outOfPlaceInd + 2;
          }

          else
          {
            return;
          }
    }
  }





    public static void main( String[] args ) {
        PQHeap<Integer> pq = new PQHeap<Integer>(new TestIntComparator());

            pq.add( 10 );
            pq.add( 20 );

            System.out.println(pq.size());
            pq.add( 20 );
            pq.add( 30 );



        class TestIntComparator implements Comparator<Integer> {
            public TestIntComparator() {;}

            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }   
        }
    }

}

// class NaturalComparator<T extends Comparable<T>> implements Comparator<T> {
//   public int compar(T a, T b) {
//     return a.compareTo(b);
//   }
// }

1 Ответ

0 голосов
/ 27 ноября 2018

В конструкторе PQHeap вы не назначаете входной объект сравнения в поле класса.Добавьте строку как это: 

this.comparator = comparator;

в вашем конструкторе

...