0

似乎找不到问题，现在我的代码有点迷失了......真的可以用更好的眼光。真的很感激。

这是错误：

Exception in thread "main" java.lang.NullPointerException
    at Heap.<init>(Heap.java:16)
    at Heap$1.<init>(Heap.java:131)
    at Heap.main(Heap.java:131)

http://codepaste.net/jogkx2

public abstract class Heap {

    private List heap_array; // Arraylist containing heap.
     private List<ELEM> priority_queue; //ArrayList containing ELEMS.
     private int heapsize; // Maximum heapsize of the heap.
     private int n; // Number of elements currently in the heap.
     private int last_elem = heap_array.size()-1; // last elem in the heap


     public Heap(int s, int n) {
        heap_array = new ArrayList();
          priority_queue = new ArrayList<ELEM>();
          s = heapsize;
          n = this.n;
    }

    protected int returnMaxPriority(){
        int max = priority_queue.get(priority_queue.size()-1).getLocation();
        return max;
        }

    public void shiftDown(int i) {
        int leftChild = leftChild(i);
        int rightChild = rightChild(i);
        int largest = i;

            // Max Heapify
        if (leftChild < heap_array.size() 
          && !aboveOrEqual(largest, leftChild)) {
            largest = leftChild;
        }
        if (rightChild < heap_array.size() 
          && !aboveOrEqual(largest, rightChild)) {
            largest = rightChild;
        }

        if (largest != i) {
            switchElems(largest, i);
            shiftDown(largest);
        }
    }

    public void insert(Object obj, int priority) {
              heap_array.add(obj);
              int object_i = 0;
             while (object_i > 0 && !aboveOrEqual(parent(object_i), object_i)) {
          switchElems(parent(object_i), object_i);
          object_i = parent(object_i);
             }
            // enqueue(object_i, priority);
    }

    public Object removeLast() {
        if (heap_array.size() > 0) {
            switchElems(0, last_elem);
            Object result = heap_array.remove(last_elem);
               shiftDown(0);
            return result;
        } else {
            return null;
        }
    }


    public Object get(int index) {
        return heap_array.get(index); //Return object
    }

    public int heapsize() {
        return heap_array.size();
    }

    protected int parent(int i) {
        return (i - 1) / 2;
    }
     protected void update_N(int n){
             n = this.n;
     }

      protected void update_Size(int size){
             heapsize = size;
     }

    protected int leftChild(int i) {
        return 2 * i + 1;
    }

    protected int rightChild(int i) {
        return 2 * i + 2;
    }

    protected void switchElems(int i, int j) {
        Object tmp = heap_array.get(i);
        heap_array.set(i, heap_array.get(j));
        heap_array.set(j, tmp);
    }


    public void enqueue(int object_i, int priority) {
           ELEM tmp = new ELEM(priority, object_i);
          priority_queue.add(object_i, tmp);
        }


     public int dequeue() {
     if (heap_array.size() > 0) {
     int max_location = returnMaxPriority();
         heap_array.remove(max_location);
        return max_location;
        }
        else{return -1;}
     }

     public void changeWeight(int object_i, int priority){
           ELEM tmp = new ELEM(priority, object_i); 
           priority_queue.set(object_i, tmp);
     }

     protected abstract boolean aboveOrEqual(int value1, int value2);

    public static void main(String[] args){
        Heap h = new Heap(100, 20) {
            protected boolean aboveOrEqual(int value1, int value2) {
                return ((Integer)get(value1)).intValue() 
                     >= ((Integer)get(value2)).intValue(); //Compares the objects int values.
            }
        };

        System.out.println("Enter a list of numbers, then type quit: ");


          for (int i = 0; i < 100; i++) {
            h.insert(new Integer((int)(100 * Math.random())), i);
        }
    }
}

class sortPriorityArray implements Comparator<ELEM> {
    @Override
    public int compare(ELEM s1, ELEM s2){
        int value1 = s1.getPriority();
        int value2 = s2.getPriority();

        if(value1 < value2){
        return 1;
        }
        else if(value2 > value1){
        return -1;    
        }
        return 0;
    }

如果你也可以看看我的插入函数和 returnmax。类 ELEM 包含优先级和位置，因此我可以通过按优先级对 priority_queue 进行排序，然后首先使最高优先级出列，以正确的顺序出列。

4

3 回答 3

1

n = this.n;可能是罪魁祸首。您试图this.n在初始化它之前引用它。您将要避免this在构造函数中使用，除非您正在初始化（而不是引用）this.

编辑：我猜你的意思是this.n = n;？刚看到你的评论，我想这解释了它。:)

于 2013-07-26T22:26:53.027 回答
1

这里抛出异常

private int last_elem = heap_array.size()-1; // last elem in the heap

此时 heap_array 还没有被初始化，所以它是null。最简单的解决方案是将其移至构造函数或将其设置为

private int last_elem = -1; // last elem in the heap

因为这会做同样的事情。

顺便说一句，如果您想知道如何自己解决这个问题，您可以在调试器中单步执行代码，它是 IDE 中运行旁边的按钮。

于 2013-07-26T22:31:20.430 回答
1 
private int last_elem = heap_array.size()-1; // last elem in the heap

此行调用size()尚未初始化的列表。

于 2013-07-26T22:28:49.590 回答