0

ヒープソートを使用して配列をソートする関数を作成しています。これまでのところ、私は持っています:

template <typename Item, typename SizeType>
void heap_sort(Item data[], SizeType size) {
vector<int> v(data,data+size);
SizeType unsorted = size;

make_heap(v.begin(),v.end());

while(unsorted > 1) {
    --unsorted;
    swap(data[0], data[unsorted]);
    reheapify_down(data,unsorted);
}
}

と：

template <typename Item, typename SizeType>
void reheapify_down(Item data[], SizeType size) {
SizeType current(0), big_child;
bool heap_ok = false;

while(!heap_ok && 2*current+1 < size) {
    if(2*current+2 > size)
        big_child = 2*current + 1;
    else if(data[2*current+1] > data[2*current+2])
        big_child = 2*current+1;
    else
        big_child = 2*current + 2;

    if(data[current] < data[big_child]) {
        swap(data[current],data[big_child]);
        current = big_child;
    }
    else
        heap_ok = true;
}
}

プログラムを実行すると、正しくソートされていない配列が出力されます。見逃しているものや見落としているエラーはありますか?

4

1 に答える 1

0

ほんのいくつかの提案。

まず、コレクションに対して 1 から始まるインデックスを使用できるようにするだけの小さなプロキシ クラスを作成します。ヒープで使用されるすべてのインデックス計算は、1 ベースのインデックス作成を想定しており、すべてのコード全体で 1 か所で 0 ベースのインデックス作成を補うよりもはるかに簡単です。reheapify_down現時点では、インデックス作成をたどってあなたが正しいことを確認するのに十分な時間を費やしています. これは確かに正しい一般的な考え方ですが、すべての数学が正しいことを確認するには多くの作業が必要です。

第二に、あなたとあなたのcheck_heap両方を検証するために使用できる a (または何でも) を作成します(余談ですが、「make_heap」または「heapify」のいずれかを決定するため、名前は「make_heap」と「make_heap」のいずれかになります) "remake_heap"、または "heapify" および "reheapify")。make_heapreheapify_down

ただし、それを超えて、特にmake_heap質問にコードを含めていないため、問題を特定するのは困難です。それが正しく機能しない場合、残りは望みがありません。

于 2012-12-06T21:54:26.940 に答える