1

私は問題を解決するために最小ヒープを学習して実装しようとしています:doubleを作成し、それらをソートされた配列に挿入するループ、C

基本的に、私は最小から最大にソートされたダブルのセットから始めます。次に、doubleを(おそらくランダムに)生成し、新しく生成されたdoubleを、ソートしたままセットに追加する必要があります。また、ダブルを挿入するたびに、セットから最小のダブルを削除します。

編集-セットを完全にソートする必要はありません。目標は、doubleを挿入するたびに最小要素を検索して削除できるようにすることです。セットをソートしたままにすることが、私の最初の素朴な解決策でした。)

最小ヒープが実行されたようなもののように聞こえます。

試み

Cでは、配列サイズが事前に宣言されているため、長さ=最終的に得られるdoubleの最大数の配列を作成する必要があります。次に、この配列のすべてのエントリに値max_doubleを入力します。

ここでガイドとして説明されているメソッドを使用して:http://opendatastructures.org/versions/edition-0.1e/ods-java/10_1_BinaryHeap_Implicit_Bi.html、この配列に値を挿入および削除する関数を作成できます。

挿入:配列の最後のエントリ(常にmax_doubleになります)を数値に置き換えます。次に、親ノードの値が新しく追加された値より小さくなるまで、親ノードの値と交換し続けます。

削除:ルートノードをmax_doubleに置き換えてから、その2つの子と比較し、2つの子がmax_doubleになるまで最小の子と交換します。

質問

私はこれらすべてに正しいアプローチを使用していますか?

4

1 に答える 1

4

ヒープは配列をソートしません。これは単純にルールに従います。つまり、最小ヒープでは、親は常に子よりも小さくなります。残念ながら、子供たちは秩序を保つ必要はありません。

ヒープを配列に実装したい場合は、wikiにそれに関するすばらしいページがあります。

http://en.wikipedia.org/wiki/Binary_heap

もう少し説明:

挿入:要素を配列の最後に追加します(置換なし!)順序が正しい場合は、要素を親at(i-1 / 2)と比較します。それ以外の場合は、交換して手順2を再度実行します。(現在のインデックスを更新することを忘れないでください)

削除:最小値を配列の最後の要素と交換します最後の要素を削除します上から順に、ルートとその子を比較し、最小のものと交換します。それ以外の場合は停止します。条件が満たされるか、他に子供がなくなるまで、子供と比較し続けます。

0から始まるインデックスの場合、親はfloor((i-1)/ 2)にあり、子は2i+1と2i+2にあります。

もう1つ、ダブルを格納するためにdequeを使用することをお勧めします。

于 2012-09-29T16:07:21.620 に答える