最大ヒープの実装

Question

Javaの次のMaxHeapの実装にはどのような修正を加える必要がありますか？挿入機能は、呼び出されると実行を継続します。 Insert関数とBuildHeap関数のエラーは何ですか？私はPercolateDown関数を編集しました。私はそれが今正しいと思う..？

public class MaxHeap { 
    public int[] array; 
    public int count; 
    public int capacity; 
    public MaxHeap(int capacity){ 
     this.capacity=capacity; 
     this.count=0; 
     this.array=new int[capacity]; 
    } 
    public int Parent(int i){ 
     if(i<=0 || i>=this.count) 
      return -1; 
     return 
       (i-1)/2; 
    } 
    public int LeftChild(int i){ 
     int left=2*i+1; 
     if(left>=this.count) 
      return -1; 
     return left; 
    } 
    public int RightChild(int i){ 
     int right=2*i+2; 
     if(right>=this.count) 
      return -1; 
     return right; 
    } 
    public int GetMaximum(){ 
     if(this.count==0) 
      return -1; 
     return this.array[0]; 
    } 
    public void PercolateDown(int i){ 
     int l,r,max,temp; 
     l=LeftChild(i); 
     r=RightChild(i); 
     if(l!=-1 && this.array[l]>this.array[i]) 
      max=l; 
     else 
      max=i; 
     if(r!=-1 && this.array[r]>this.array[max]) 
      max=r; 
     if(max!=i){ 
      temp=this.array[i]; 
      this.array[i]=this.array[max]; 
      this.array[max]=temp; 
     } 
     if(max==i){return;} 
     PercolateDown(max); 
    } 
    public int DeleteMax(){ 
     if(this.count==0) 
      return -1; 
     int data=this.array[0]; 
     this.array[0]=this.array[this.count-1]; 
     this.count--; 
     PercolateDown(0); 
     return data; 
    } 
    public void Insert(int data){ 
     int i; 
     if(this.count==this.capacity){ 
      ResizeHeap(); 
     } 
     this.count++; 
     i=this.count-1; 
     while(i>=0 && data>this.array[(i-1)/2]){ 
      this.array[i]=this.array[(i-1)/2]; 
      i=(i-1)/2; 

     } 
     this.array[i]=data; 
    } 
     public void ResizeHeap(){ 
      int[] array_old=new int[this.capacity]; 
      for(int i=0;i<this.capacity;i++){ 
       array_old[i]=this.array[i]; 
      } 
      this.array=new int[this.capacity*2]; 
      for(int i=0;i<this.capacity;i++){ 
       this.array[i]=array_old[i]; 
      } 
      this.capacity*=2; 
      array_old=null; 

    } 
     public static MaxHeap BuildHeap(int[]A,int n){ 
      MaxHeap h=new MaxHeap(n*2); 
      if(A==null)return h; 
      //while(n>h.capacity) 
       //h.ResizeHeap(); 
      h.capacity=n*2; 
      for(int i=0;i<n;i++){ 
       h.array[i]=A[i]; 
      } 
      h.count=n; 
      for(int i=(n/2)-1;i>=0;i++){ 
       h.PercolateDown(i); 
      } 
      return h; 
    } 
     public void Delete(int i){   
      if(this.count<i){ 
       System.out.println("Wrong Position"); 
       return; 
      } 
      this.array[i]=this.array[this.count-1]; 
      this.count--; 
      PercolateDown(i); 

     } 

     public static void main(String[] args){ 
      //int[] A={7,6,5,4,3,2,1}; 
      //int len=A.length; 
      //MaxHeap h=BuildHeap(A,len); 
      //for(int i=0;i<len;i++){ 
       //System.out.print(h.array[i]+" "); 
      //} 
      MaxHeap h=new MaxHeap(10); 
      h.Insert(7); 
      System.out.print(h.array[0]); 
     } 
} 

Answer 1

私はInsert()にwhileループ内でこの文を挿入：

 System.out.println(i); 

をそれが0たびに出力します。 0> = 0で、配列にも0が入っているので、データが7と7> 0のとき、while条件はtrueです。ループ内でiを(i - 1)/2に設定しています。これは-1/2です。これは0に丸められ、再び0になります。したがってiは変更されず、while条件は引き続きtrueになります。これがあなたのループが決して止まらない理由です。私はあなたがどのように働く方法を意図しているのか理解していないので、私は示唆を与えていない。

BuildHeap()のforループ内で同じprintステートメントを試してみると、オーバーフローして突然ネガティブになるまで増加していることがわかります（可能な限り高い整数に1を加えれば、 2147483648）。私はあなたがi--ではなくi++をfor(int i=(n/2)-1;i>=0;i++){で意図していたと思います。