高速な挿入が可能で、挿入のたびに重複することなくデータをソートできるデータ構造を実装したいと思います。
二項ヒープについて考えましたが、その構造について理解したのは、特定の要素がまだヒープにあることを挿入中に判断できないということです。一方、私のケースに完全に適合するAVLツリーがありますが、正直なところ、現時点では実装するには難しすぎます。
私の質問は次のとおりです。二項ヒープ挿入アルゴリズムを編集して重複をスキップする可能性はありますか? たぶん、誰かが別の構造を提案できますか？
グレッティング:)
C++ にはstd::set. 内部的には、赤黒の木の実装です。データを入力するとソートされますので、参考にしてみてください。
O(log(n))これに適したデータ構造は、挿入用の赤黒木です。これを行うデータ構造を実装したいとおっしゃいました。それを実装する方法の適切な説明は、こちらと、オープン ソースの使用可能なライブラリです。
スレッドセーフに関心がある場合は、スキップリストも可能です。スキップリストはリバランスを必要とせず、スキップリストも本質的にBSTのようにソートされるため、バランスの取れた二分探索木はスキップリストよりもパフォーマンスが低下します。必要なメモリの量には不利な点がありますが (技術的には複数のリンクされたリストが使用されるため)、理論的にはうまく収まります。
スキップ リストの詳細については、このチュートリアルを参照してください。
要素の数が非常に多い場合は、二重リンク リストを使用して、すべての項目が挿入された後にリストを並べ替えることも検討してください。これには、実装と挿入時間の容易さという利点があります。
次に、並べ替えアルゴリズムを実装する必要があります。選択ソートまたは挿入ソートは、マージソート、ヒープソート、またはクイックソート アルゴリズムよりも低速ですが、実装が簡単です。一方、後者の 3 つの実装もそれほど難しくありません。注意すべき唯一のことは、これらのアルゴリズムは通常再帰を使用して実装されるため、スタックをオーバーフローさせないことです。独自のスタック実装を作成し (難しくありません)、必要に応じて値をスタックにプッシュおよびポップして、それらを繰り返し実装することができます。私が言及しているものの例については、反復クイックソートを参照してください。
ライブラリの使用に問題がなければ、libavl を参照してください。この ライブラリには、他の種類のバイナリ ツリーも実装されています。
高速な挿入と簡単な実装を探しているなら、なぜリンクされたリスト (シングルまたはダブル) を使わないのですか? 挿入: プッシュ ヘッド/プッシュ テール - O(1) 削除: ポップ ヘッド/ポップ テール - O(1) 唯一の「検索」は O(n) になります