0

最小ヒープの形式で配列を表現しようとしています。そして、親が右の子よりも大きい (12 より大きい 6) リーフ ノードの 1 つで問題に直面しています。コーディングの何が問題なのか理解できません。助けてください。

これが私のコードです：

public class MinHeap {

public void heapify(int Array[], int i){

    int min;
    int left=2*i;
    int right= 2*i+1;

    int length=Array.length;

    if(left<length &&  Array[left]< Array[i] && Array[left]< Array[right])
        min=left;
    else if(right<length && Array[right]<Array[i] && Array[right]<Array[left])
        min=right;
    else min=i;

    if(min!=i){
        int temp=Array[i];
        Array[i] = Array[min];
        Array[min]=temp;
        heapify(Array,min);
    }
}

public void display(int Array[]){
    for(int i=0; i<Array.length; i++)
        System.out.print(Array[i]+" ");
}

public static void main(String[] args){
    int Array[]={2,1,4,5,6,100,0,9,8,3,12,32,6,7,1000,999,20};
    //int Array[]={1, 8, 9, 2, 10, 14, 3, 4, 7, 16};
    int length=Array.length;

    MinHeap object= new MinHeap();
    System.out.println(length);

    object.display(Array);
    System.out.println();

    for(int i=(length/2)-1;i>=0;i--){
        object.heapify(Array,i);

    }

    System.out.println();
    object.display(Array);
}

}

私が得ている出力は次のとおりです。

0 1 3 2 4 12 5 9 8 6 100 32 6 7 1000 999 20
4

2 に答える 2

0

これを試して。

static void heap(int[] a) {
    for (int i = 0; i < a.length; ++i) {
        while (true) {
            int p = (i - 1) / 2;
            if (a[p] <= a[i])
                break;
            int t = a[i];
            a[i] = a[p];
            a[p] = t;
            i = p;
        }
    }
}

と

int a[]={2,1,4,5,6,100,0,9,8,3,12,32,6,7,1000,999,20};
heap(a);
System.out.println(Arrays.toString(a));
// -> [0, 2, 1, 5, 3, 6, 4, 9, 8, 6, 12, 100, 32, 7, 1000, 999, 20]
于 2016-03-17T00:51:28.813 に答える
0

あなたの子供のインデックスは間違って計算されています。以下を使用する必要があります。

int left=2*i+1;
int right=2*i+2;

出力は次のようになります。

0 1 2 5 3 6 4 9 8 6 12 32 100 7 1000 999 20

于 2016-03-17T00:51:45.060 に答える