0

私はアルゴリズムが初めてで、ヒープソートアルゴリズムを実装したいと考えていました。アルゴリズムは次のように与えられます。

Parent(i) return Math.floor(i/2)

左(i) リターン 2i

右(i) 2i+1 を返す

次に、ヒープ プロパティを復元する HEAPIFY メソッドがあります。アルゴリズムは次のとおりです。

HEAPIFY(A, i)
 l = Left(i)
 r = Right(i)
 if (l <= heap-size[A] and A[l] > A[i]
  then largest = l
 else largest = i
 if r <= heap-size[A] and A[r] > A[largest]
  then largest = r
 if largest != i
  then exchange A[i] <-> A[largest]
       HEAPIFY(A, largest)

このメソッドを実装する私のコードは次のとおりです。

public static void HEAPIFY(int[] A, int i) {
    int l = LEFT(i);
    int r = RIGHT(i);
    int largest = 0;
    if (l < A.length && A[l] > A[i]) {
        largest = l;
    } else {
        largest = i;
    }

    if (r < A.length && A[r] > A[largest]) {
        largest = r;
    }

    if (largest != i) {
        int temp = A[i];
        A[i] = A[largest];
        A[largest] = temp;
        HEAPIFY(A, largest);
    }
}

今、私の質問は本にあります アルゴリズムは、ヒープと配列のツリーを描画することによって示されているため、たとえば配列は [16,14,10,8,7,9,3,2,4,1] であり、ツリーとまた、配列の場合は、1 から n までのインデックスが付けられるため、Array[1] = 16 であり、コーディングでは Array[0] = 16 です。今、インデックス 1 から開始して 1 まで上昇するように heapify メソッドを調整することはできません。 0 から開始し、ヒープに 0 から n-1 までのインデックスを付けます。

混乱している場合は申し訳ありませんが、私はまだ混乱していますが、助けていただければ幸いです。

君たちありがとう

HEAPIFY が機能するようになりました。次のコードは、ヒープを構築するためのコードです。

public static void BUILD_HEAP(int[] A) {
    heapSize = A.length;
    for (int i = (int) Math.floor(A.length / 2.0); i >= 0; i--) {
        HEAPIFY(A, i);
    }
}

ヒープの構築も機能し、機能しない唯一の方法はヒープソートです。

 public static void HEAPSORT(int[] A) {
    BUILD_HEAP(A);
    for (int i = A.length-1; i >= 1; i--) {
        int temp = A[0];
        A[0] = A[i];
        A[i] = temp;
        heapSize = heapSize-1;
        HEAPIFY(A,0);
    }
}

これはソートする必要がありますが、ヒープソートの呼び出し後に配列をトラバースしようとすると、ソートされた配列が得られません。ヒープソートを修正する方法はありますか?

4

2 に答える 2

1

Parent(i) return Math.floor(i/2)

=> Parent(i) return Math.floor((i - 1) / 2)

左(i) リターン 2i

=> 左 (i) 2i + 1 を返す

右(i) 2i+1 を返す

=> 右 (i) 2i + 2 を返す

これは、いじる (私が実際に行ったことです) か、j = i - 1 を考慮することで解決できます。

i' = 2 i かつ j = i - 1 の場合 i = j + 1

j' = i' - 1 = (2i) - 1 = (2(j + 1)) - 1 = 2j + 1

于 2012-06-21T03:53:39.987 に答える
0

フォーム インデックス 1 から開始する場合は、[-x,16,14,10,8,7,9,3,2,4,1] -x は配列 [0] のように配列を初期化できます。つまり、配列[0]にある要素は無視できます。

インデックス 0 から開始する場合は、関数 LEFT(i) と RIGHT(i) を変更する必要があります。

LEFT(i) 2*i+1 を返します。

RIGHT(i) 2*i+2 を返します。

于 2012-06-21T05:12:37.983 に答える