次の制約を持つ両端優先キューを実装したいと思います。
固定サイズの配列で実装する必要があります..たとえば100個の要素..配列がいっぱいになった後に新しい要素を追加する必要がある場合は、最も古い要素を削除する必要があります
O(1) の最大値と最小値が必要
可能であれば O(1) に挿入
可能であれば、O(1) の最小値を削除します
可能であれば、O(1) の空/初期状態にクリア
O(1) の現時点での配列の要素数のカウント
上記の 5 つの操作すべてに O(1) を使用したいのですが、同じ実装ですべての操作に O(1) を使用することはできません。少なくとも 3 つの操作で O(1)、他の 2 つの操作で O(log(n)) で十分です。
そのような実装へのポインタを提供できるかどうかを評価します。
最大値と最小値を O(1) にする必要がある場合は、最小値、最大値、およびサイズを常に追跡し、すべてのノードをある種のツリー構造にリンクするリンク リストを作成します。おそらくヒープ。最小、最大、およびサイズはすべて一定であり、任意のノードを見つけると O(log n) になるため、挿入と削除はそれぞれ log n になります。クリアは簡単です。
キューが固定サイズの場合、O 表記は無意味です。O(log n) または O(n) 操作は基本的に O(1) です。これは n が固定されているためです。したがって、本当に必要なのは、特定のデータセットに対して高速なアルゴリズムです。おそらく、2 つの並列の従来のヒープ優先度キュー (1 つは高用、もう 1 つは低用) で問題ありません。
持っているデータの種類について詳しく知っていれば、より特別な目的のものを作成できるかもしれません。