2

最大ヒープを実装する次のJavaコードがあります。正しく動作します、

番号のリスト：4、1、3、2、16、9、10、14、8、7

MaxHeapの結果：

16 14 10 8 7 9 3 2 4 1

私が欲しいのは、このコードを変更して、インデックスを指定し、Max-Heapを配列の一部のみにすることです。

たとえば、index=4を指定した場合

最初の4つの要素に影響を与えるべきではありません：4 1 3 2が、残りの要素で最大ヒープを作成する16、9、10、14、8、7

したがって、最終結果は次のようになります。

4 1 3 2 16 14 10 9 8 7

他のアレイは使用しないでください。指定されたアレイのみを使用してください。

public class Heapify {

    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) {

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

    public static void heapMe() {
        int kk;
        for (kk = (Arr.length) / 2 - 1; kk >= 0; kk--) {
            heapify(Arr, kk);
        }
    }

    public static void heapify(int[] Arr, int i) {
        int largest;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        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);
            heapify(Arr, largest);
        }
    }

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

1 に答える 1

2

nを参照する関数にパラメータを追加し、へのすべての参照をに置き換える必要がありArr.lengthます。に渡すと、最初の4つの要素が山積みになります。Arr.lengthn4heapMe

public static void heapMe(int n) {
    int kk;
    for (kk = n / 2 - 1; kk >= 0; kk--) {
        heapify(Arr, n, kk);
    }
}

public static void heapify(int[] Arr, int n, int i) {
    ... // Replace Arr.length with n throughout the body of the function
}
于 2013-02-27T03:02:40.590 に答える