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 条件为真。在您设置i为的循环内(i - 1) / 2，这是 -1 / 2，它向零舍入，再次产生 0。所以i没有改变，你的 while 条件仍然是真实的。这就是为什么你的循环永远不会停止的原因。我不明白你打算如何工作，所以我不敢提供建议。

在 for 循环中尝试相同的 print 语句BuildHeap()显示 i 一直在增加，直到它溢出并突然变为负数（如果你将一个加到你可以拥有的最高 int 上，你会得到最低可能的负值，-2147483648）。i--我想你本来打算i++在for(int i=(n/2)-1;i>=0;i++){.

于 2016-10-07T12:50:18.400 回答