2

次のコードを使用して、JavaでMax-Heapを作成しようとしています。

public class Heapify {
// 16 14 10 8 7 9 3 2 4 1

    public static int[] Arr = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    public static int counter = 0;

    public static void main(String[] args) {
        int kk;
        for (kk = 0; kk <= Arr.length - 1; kk++) {
            heapM(Arr, kk);
        }

        for (int krk = 0; krk < Arr.length; krk++) {
            System.out.println(Arr[krk]);
        }



    }

    public static void heapM(int[] Arr, int i) {

        int largest;
        int left = i * 2;
        int right = i * 2 + 1;
        if (((left < Arr.length) && (Arr[left] > Arr[i]))) {
            largest = left;
        } else {
            largest = i;
        }

        if (((right < Arr.length) && (Arr[right] > Arr[largest]))) {
            largest = right;
        }
        if (largest != i) {
            swap(i, largest);


            heapM(Arr, largest);
        }
    }

    private static void swap(int i, int largest) {
        int t = Arr[i];
        Arr[i] = Arr[largest];
        Arr[largest] = t;

    }
}

必要な出力は次のとおりです。

16 14 10 8 7 9 3 2 4 1

私が得ているのに対して

4 3 16 14 8 9 10 2 1 7

ヒープが適切に構築されていない理由について誰かが助けてもらえますか？

ありがとう

4

5 に答える 5

6

あなたのコードを実行したところ、城高が言ったことに加えて、もう 1 つエラーが見つかりました

for (kk = 0; kk <= Arr.length - 1; kk++) {
        heapM(Arr, kk);
}

する必要があります

for (kk = Arr.length -1; kk >= 0; kk--) {
        heapM(Arr, kk);
}

MaxHepify を実行するときは、最後から開始し、逆方向に進むためです。と

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

あるべきだ、城高が言ったように

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

ここで実行したところ、出力が正しくなりました

于 2012-07-17T18:43:07.360 に答える
4

あなたの問題はここにあると思います：

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

Java 配列はゼロベースなので、0 の左の子は 0 * 2 = 0 です! ロジックを修正して、問題が解決するかどうかを確認してください。

于 2012-07-17T18:35:47.923 に答える
2 
for (kk = Arr.length -1; kk >= 0; kk--) {
    heapM(Arr, kk);
}

する必要があります

for (kk = (Arr.length -1)/2; kk >= 0; kk--) {
    heapM(Arr, kk);
}

もっと効率的。

編集これにより、O(n*lg(n)) 時間ではなく O(n) 時間でヒープを構築できます。

于 2013-03-29T21:12:44.133 に答える
1

最大ヒープを作成したいので、0からnではなくn/2から0まで開始する必要があります。0からnのために、2 0 11213のような配列で何が起こるかということです。最大ヒープを実行した後の出力配列は2131 12 0になりますが、n/2から0まで呼び出す場合は次のようになります。 13 12 120。

于 2012-07-17T18:44:33.937 に答える
1

これは宿題ですか？そうでない場合は、JAVA の PriorityQueue を使用できます

于 2012-07-17T19:42:17.547 に答える