ランダムな順序で到着するが、指定された順序で処理および/またはスタックから削除する必要があるデータを処理するための適切に効率的なストレージ構造を探しています。
これを明確にするために:
各アイテム x にはインデックス i、タイムスタンプ t があり、次のように処理されます (ストレージ構造が既に設定されていると仮定します)。
repeat
1) Process (remove) the item with the smallest time stamp.
2) Add new items (0 or more).
3) Remove (0 or more) items (referenced by their index).
until false
各アイテムが一意のタイムスタンプとインデックスを持つことが保証されています。しかし、ステップ 1) が完了するまで、ステップ 2) でいくつの項目が追加されるか、またはステップ 1) と 2) がアルゴリズムの各ループ内で完了するまで、ステップ 3) でいくつの項目が削除されるかを予測することは不可能です。着信アイテムのタイムスタンプの分布は予測できず (新しいタイムスタンプが「将来」になることを除いて)、時間とともに変化する可能性があります。またはそれ未満) リストに残っている項目のいずれか。一度に処理されるのを待っている要素の最大数がありますが、これはかなり大きくなる可能性があります ~10^6-10^8,
ステップ 2) で到着した各アイテムをリンクされたソート済みリストに追加すると、ステップ 1) は O(0) になりますが、ステップ 2) は O(n) になります。二分木を使用すると、ステップ 1) はまだ O(1) であり、ステップ 2) は最初は O(log n) ですが、タイムスタンプが適切に分散されていないと、ツリーが非常に急速に不均衡になり、ステップ 2) が遅くなる可能性があります。大幅にダウンします(定期的にツリーのバランスを取り直さないと、最終的にはO(n)よりも良くなりません)。
私の推測では、定期的なリバランスを行うバイナリ ツリーに沿ったものは、リバランスが適切な間隔で行われる場合、O(log n) を提供するはずですが、この種の問題は十分に解決されていると思います。誰かが私に適切なリファレンスを教えてくれるか、車輪の再発明を避けるのに役立つちょっとしたアドバイスをくれませんか.