java - 最大堆实现

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。所以 i 没有改变，你的 while 条件仍然为真。这就是为什么你的循环永远不会停止。我不明白你的方法是如何工作的，所以我不敢给出建议。

在 BuildHeap() 的 for 循环中尝试相同的 print 语句会发现 i 不断增加，直到溢出并突然变为负值(如果您将 1 添加到您可以拥有的最高 int 值，您将获得尽可能低的负值，-2147483648)。我认为您在 for(int i=(n/2)-1;i>=0;i++){ 中的意图是 i-- 而不是 i++。