2

私は、Java でのヒープ ソートの実装に関する宿題の問題に取り組んでいます。これが私がこれまでに持っているものです

public class HeapSort {

    public static void maxHeapify(int[] a, int i) {
        int largest;
        int l = 2*i;
        int r = (2*i)+1;
        if (l<=a.length-1 && a[l]>a[i]) {
            largest = l;
        }
        else {
            largest = i;
        }
        if (r<a.length-1 && a[r]>a[largest]) {
            largest = r;
        }
        if (largest != i) {
            int temp = a[i];
            a[i] = a[largest];
            a[largest] = temp;
            maxHeapify(a,largest);
        }
    }

    public static void buildMaxHeap(int[] a) {
        for (int i=(a.length-1/2); i>=1; i--) {
            maxHeapify(a,i);
        }
    }

    public static void heapSort(int[] a) {
        buildMaxHeap(a);
        for (int i=a.length-1; i>=1; i--) {
            int temp = a[0];
            a[0] = a[i];
            a[0] = temp;
            maxHeapify(a,1);
        }
    }

これは、テストのためにまとめたメインです（出力あり）

public static void main(String[] args) {
    int[] tester = {3,2,9,45,7,15,21,11,36};
    System.out.println(Arrays.toString(tester));
    heapSort(tester);
    System.out.println(Arrays.toString(tester));
}

[3, 2, 9, 45, 7, 15, 21, 11, 36]
[3, 45, 36, 21, 9, 15, 2, 11, 7]

現在、エラーは発生していませんが、出力が少しずれています。どんな助けでも大歓迎です。ありがとう！

*サンプル出力を追加するために編集されました

4

2 に答える 2

2

一見すると、maxHeapify() への多くの呼び出しが欠落していると思います。ヒープの半分 (一番右のブランチで終わる半分) だけを maxHeapify() したように見えますが、残りはそうではありません。a[0] から a[length/2] までのすべての要素に対して maxHeapify() を呼び出す必要があります。

スワップの条件から maxHeapify() への再帰呼び出しを移動する必要があります。ヒープの初期構築では、ルートまで伝搬する必要があります。そして、「最大の」要素を maxHeapify() するのではなく、ヒープを 1 つレベルアップするので、常にi/2.

于 2013-02-22T07:24:37.993 に答える
0 
    if (r<a.length-1 && a[r]>a[largest]) {
        largest = r;
    }

する必要があります

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

最後のループのmaxHeapify(a,0);代わりに呼び出す必要があると思います。maxHeapify(a,1);それとは別に、上記のコメントの-1/2の順序の問題。それは仕事をするはずです。

于 2013-02-22T07:31:58.243 に答える