0

ウィッチヒープソートに問題があります。コードのどこが悪いのかわかりません。このプログラムは、テーブルの2番目と最後の位置のみを変更しました。これは私のコードです（メイン関数なし）：

   #include<stdio.h>
#define DUZO 100000000
int heap_size;
int tab[DUZO];

void heapify(int start){
    int l, r, largest, pom;

    l = 2*start + 1;
    r = 2*start + 2;

    if((l < heap_size) && (tab[l] > tab[start]))
        largest = l;
    else
        largest = start;

    if((r <  heap_size) && (tab[r] > tab[largest]))
        largest = r;
    if(largest != start){
        pom = tab[start];
        tab[start] = tab[largest];
        tab[largest] = pom;

        heapify(largest);
    }
}

void build_max(){
    int lenght, i;
    lenght = heap_size;

    for(i = ((lenght - 1)/2); i >= 0; --i){
        heapify(i);
    }
}

void heap_sort(){
    int i;
    build_max();


    for(i = heap_size-1; i > 0; --i) {
        int tmp = tab[0];
        tab[0] = tab[i];
        tab[i] = tmp;
        --heap_size;
        heapify(0);
    }
}

すべての助けをありがとう。

4

1 に答える 1

1 
int heap_size = 6;
int tab[5];

これは、配列の末尾を超えて書き込み (および読み取り) を行う必要があり、未定義の動作を引き起こし、おそらく悪い結果をもたらします。

ヒープ サイズと配列をグローバル変数として持つのは悪い考えです。これらは関数の引数にする必要があります。

l = 2*start + 1;
r = 2*start + 2;

これは、インデックス 0 にヒープのトップがある場合のインデックス付けですが、

if((l <= heap_size) && (tab[l] > tab[start]))

そのチェックは、インデックス 1 にヒープのトップがある場合に使用されます。インデックス 0 の場合は、それが必要です<(次の のチェックでもr)。

void build_max(){
    int lenght, i;
    lenght = heap_size;

    for(i = ((lenght - 1)/2); i > 0; i--){
        heapify(i);
    }
}

トップをヒープ化するのを忘れているため、通常はヒープを作成しません。条件はi >= 0.

void heap_sort(){
    int i, lenght;
    build_max();
    lenght =  heap_size;

    for(i = lenght; i > 1; i--){
        heap_size -= 1;
        heapify(i);
    }
}

最後の位置でヒープのトップをスワップしないため、まったくソートされません。ループは次のようになります

for(i = heap_size-1; i > 0; --i) {
    /* swap top of heap in the last position */
    int tmp = tab[0];
    tab[0] = tab[i];
    tab[i] = tmp;
    --heap_size; /* urk, but what can we do if heapify uses the global? */
    heapify(0);  /* we need to heapify from the top, since that's where the leaf landed */
}

実際に配列をソートします。

于 2012-10-08T17:58:04.530 に答える