私は、かなり多くのアイテム (数千のオーダー) を保存する必要があるものに取り組んでいます。
アイテムは頻繁に挿入、削除、およびアクセスされます。ただし、アイテムの値が大きいほど、挿入、削除、またはアクセスされる可能性が高くなります。
さらに、構造内の最初の "k" 項目 ("k" はかなり小さい) の非常に迅速な並べ替えをサポートしたいと考えています。
したがって、理想的には、これらの操作を行うコストは、その価値に直接相関します。
ここでは、アイテムが常にソートされたままの単純なリンク付きリストは単純なアプローチですが、すべての場合のパフォーマンスは依然として重要です。一般的なケースでは、操作が O(n) よりも優れていることが理想的です。
私はこの問題についてかなりブレインストーミングしましたが、困惑しています。
最初はビープが理想的なデータ構造かもしれないと思っていましたが、検索はビープの上部に偏っていません。代わりに、下隅から始まり、上に向かって進みます。私が必要とするものではありません。
これらの操作は O(log n) ですが、より大きな値に対してより適切に実行したいため、いくつかのフレーバーのバイナリ検索ツリーは適切なソリューションではないようです。
私が必要としているのは、右下からトラバーサルを開始できるように、ほぼ横に反転した二分探索木です。しかし、私はそれが私にとってうまくいくかどうかを確認するために頭を包み込もうとしています. O(2 log n) 最悪の場合のパフォーマンスを提供し、より大きな値では O(log n) よりも優れていると思います...しかし、完全にはわかりません。
そのようなデータ構造はありますか？それとも、発明しなければなりませんか？