2

楽しみのためにJavaでヒープソートを試みています。

まず、max-heap を作成します。次に、最初の要素を変数 max に取り、最後の要素を未配置配列からヒープ トップに移動してから、プッシュ ダウンします。

私は 21 のエレメントを試しましたが、70% の確率で問題なく動作しました。

ありがとう。

public class HeapSort extends Sort{
    public int sort(int arr[]) {
        for (int i = 1; i < arr.length; i++) {
            // add to heap
            int p = i;
            int pp = p /2 ;
            while (p > 0 && arr[pp] < arr[p]) {
                swap(arr, p, pp);
                p = pp;
                pp = p / 2;
            }

        }   

        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            int p = 0;
            int child1 = (p << 1) + 1;
            int child2 = (p << 1) + 2;

            while (child2 < i || child1 < i) {
                if (child1 >= i) {
                    if (arr[p] < arr[child2]) {
                        swap(arr, p, child2);
                        p = child2;
                    } else { 
                        break;
                    }
                } else if (child2 >= i) {
                    if (arr[p] < arr[child1]) {
                        swap(arr, p, child1);
                        p = child1;
                    } else {
                        break;
                    }
                } else {
                    int minIdx = arr[child1] < arr[child2] ? child1 : child2;
                    int maxIdx = child1 == minIdx ? child2 : child1;

                    if (arr[p] < arr[maxIdx]) {
                        swap(arr, p, maxIdx);
                        p = maxIdx;
                    } else {

                        break;

                    }
                }
                child1 = (p << 1) + 1;
                child2 = (p << 1) + 2;
            }

        }
        return 0;

    }
    void swap(int arr[], int idx1, int idx2) {
        int tmp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = tmp;
    }
    public String toString() {
        return "HeapSort";
    }

}
4

1 に答える 1

2

ヒープソートの最初のステップでヒープを正しく構築していません。ゼロベースの配列では、2 で割る前に 1 を引く必要があります。

public class HeapSort extends Sort{ 
   public int sort(int arr[]) { 
      for (int i = 1; i < arr.length; i++) { // add to heap 
         int p = i;
         // int pp = p /2 ;  <======= Problem!
         int pp = (p-1) / 2; 
         while (p > 0 && arr[pp] < arr[p]) { 
            swap(arr, p, pp); p = pp; 
            //  pp = p / 2; // <=====Problem!
            pp = (p-1) /2;

}
于 2012-10-25T03:52:27.027 に答える