私はアルゴリズムが初めてで、ヒープソートアルゴリズムを実装したいと考えていました。アルゴリズムは次のように与えられます。
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);
}
}
これはソートする必要がありますが、ヒープソートの呼び出し後に配列をトラバースしようとすると、ソートされた配列が得られません。ヒープソートを修正する方法はありますか?