java - 数组索引超出java堆范围

Question

我知道这是一个amaetuer错误，我明白它的含义，但我不明白为什么我无法修复它。我一直在尝试一切。我试图获取一个 T 类型的数组并交换它的值，以便它正确地对应于堆的规则，其中父级总是大于 2 个子级。错误出现在我的 while 循环中

如果事情很容易解决，请不要苛刻。我一直在苦苦挣扎，似乎找不到答案。

public class myheap<T extends Comparable<T>> extends heap<T>
{ 
    // constructors of the subclass should be written this way:
    public myheap(int max) { super(max); }
    public myheap(T[] A) {super(A);}  


    public void buildheap(T[] Arr){ 
        int size = Arr.length;
        int startsize = (size-1)/2;
        for(int i=startsize;i>0;i--){
            int l = left(i);
            int r = right(i);
            T temp = null;
            while((Arr[r]!=null) && Arr[i].compareTo(Arr[r])<0){
                if (Arr[l].compareTo(Arr[r])>0){
                    temp = Arr[l];
                    Arr[l] = Arr[i];
                    Arr[i] = temp;
                }//if left is greater than right
                else        //then right must be greater than parent            
                    temp = Arr[r];
                    Arr[r] = Arr[i];
                    Arr[i] = temp;
            }//whileloop
            if((Arr[r]==null) && Arr[i].compareTo(Arr[l])<0)
                temp = Arr[l];
                Arr[l] = Arr[i];
                Arr[i] = temp;
        }//for

    }//buildheap


    public static void main(String[] args){
        String[] array = {"SH","AH","AB","YA","AY","AA","AB","LM","LL","LO"};
        myheap<String> New = new myheap<String>(array.length);
        for(int i=0;i<array.length;i++){
            New.insert(array[i]);
        }//insert
        New.buildheap(array);
        New.drawheap();
        for(int i=0;i<array.length;i++){
            System.out.println(New.deletemax() + "  ");
        }//for
        System.out.println();

    } //main

}

myheap 正在扩展的堆父类(super class)

/*
  Polymorphic priority heaps, largest value on top.
  Heap axiom.  The value at every node cannot be smaller than the values
  at each of its children nodes.
  Use internal array to implement heap "tree", with index 0 representing
  the root.  Given node index i, left(i)= 2*i+1 and right(i)=2*i+2, while
  parent(i) = (i-1)/2.
*/

class heap<T extends Comparable<T>>
{
  protected T[] H; // internal array representing heap.
  protected int size; // size of current heap, not same as H.length!
  public int size() { return size; } // size is read-only externally.
  public int maxsize() { return H.length; }
  public heap(T[] A) { H = A; size=0; } // preferred constructor
  public heap(int m) // will cause compiler warning (ok to ignore)
  {
     H = (T[]) new Comparable[m]; // downcast from Object is OK.
     size = 0;
  }

  protected int left(int i) { return 2*i+1; }
  protected int right(int i) { return 2*i+2; }
  protected int parent(int i) { return (i-1)/2; }

  // protected is important!

  // lookup heap, without delete
  public T getmax()
  { 
    if (size<1) return null; 
    return H[0];
  }

  // insert x into heap: place at end, then propagate upwards
  // returns false on failure.
  public boolean insert(T x)
  {
     if (size > H.length-1) return false;
     H[size++] = x; // place at end, inc size
     // propagate upwards
     int cur = size-1; // current position
     int p = parent(cur);
     while (cur>0 && H[cur].compareTo(H[p])>0)
     { // propagate upwards
       T temp = H[cur];
       H[cur] = H[p];  H[p] = temp;
       cur = p;  // switch current to parent
       p = parent(cur); // recalc parent
     }//while
     return true;
  }//insert

// deletetop: take last element, move to top, propagate downwards:
  public T deletemax()
  {
     if (size<0) return null;
     T answer = H[0];
     H[0] = H[--size]; // place at top:
     // now propagate downwards.
     boolean done = false;
     int i = 0; // current position
     int c = 0; // swap candidate
     while (c != -1)
     {
     int l = left(i);
     int r = right(i);
     c = -1; // swap candidate
     if (l<size && H[l].compareTo(H[i])>0) c = l; // set candidate to left
     if (r<size && H[r].compareTo(H[i])>0 && H[r].compareTo(H[l])>0) c=r;
     if (c!= -1) 
         {
         T temp = H[i];  H[i] = H[c]; H[c] = temp;
         i = c; 
         }
     }//while
     return answer;
  }//deletemax


    // but search is not log(n). Why?
  public boolean search(T x)
    {
    for(int i=0;i<size;i++) {if (x.compareTo(H[i])==0) return true;}
    return false;
    }

  public void drawheap() // use only with heapdisplay.java program
  {
      heapdisplay W = new heapdisplay(1024,768);
      W.drawtree(H,size);
  }

}//heap


public class heaps14
{
    /**public static void main(String[] args){
    heap<Integer> HI = new heap<Integer>(200);
    for(int i=0;i<100;i++) HI.insert((int)(Math.random()*1000));
    HI.drawheap();
    for(int i=0;i<100;i++) System.out.print(HI.deletemax() + "  ");
    System.out.println();
    }//main**/
}

Answer 1

您可以检查 while 中是否为 null循环，( Arr[r]!=null )但问题是你甚至无法从数组中获取值来确定它是否是 null或不。在尝试访问数组中的值之前，您应该检查索引是否在范围内，使用 r < Arr.length或类似的。