1

次の Java での MaxHeap 実装に対してどのような修正を行う必要がありますか? Insert 関数は、呼び出されたときに実行を続けます。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]);
        }
}
4

1 に答える 1

0

次のステートメントを while ループ内に挿入しましたInsert()。

        System.out.println(i);

毎回 0 を出力します。0 >= 0 であり、配列にも 0 が含まれているため、データが 7 および 7 > 0 の場合、while 条件は true です。iに設定しているループ内で(i - 1) / 2は、これは -1 / 2 であり、ゼロに向かって丸められ、再び 0 になります。Soiは変更されず、while 条件は引き続き true です。これが、ループが止まらない理由です。私はあなたがどのようにこの方法を意図していたのか理解できませんでしたので、あえて提案はしません。

の for ループ内で同じ print ステートメントを試すと、BuildHeap()i がオーバーフローして突然負になるまで増加していることがわかります (最大の int に 1 を追加すると、最小の負の値 -2147483648 が得られます)。i--ではなく意図i++していたと思いますfor(int i=(n/2)-1;i>=0;i++){。

于 2016-10-07T12:50:18.400 に答える