为什么我在比较优先级队列堆中两个索引的行上得到 null？

Question

我正在创建一个类型为 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);
//   }
// }

Answer 1

在 PQHeap 构造函数中，您没有将输入比较器对象分配给 class 字段。添加这样的行：

this.comparator = comparator;

在你的构造函数中

为什么我在比较优先级队列堆中两个索引的行上得到 null？

Why am I getting null on a line that compares two indices in my priority queue heap?

java

heap

priority-queue

comparable

comparator