私はインタビューのためにこの質問を練習していました.
次の 3 つの操作を最小限の時間で実装する最適なデータ構造::
a.) insertion.
b.) removing the oldest element.
c.) printing the largest element.
私が考えることができる最高のものは、最小/最大ヒープまたは優先キューです。操作 (a) と (c) については、ヒープが効率的ですが、よくわかりませんが、「最も古い要素を削除する」という 2 番目の操作は、ヒープを使用して効率的に実行できます。
したがって、3つの操作すべてを効率的に実装する理想的なデータ構造を提案してください。
ありがとう！
操作a、cにある種の最大ヒープと、ノードの追加キューを使用して、それらを履歴順に格納するのはどうでしょうか。フィボナッチヒープを使用すると、操作aとcにO（1）時間、 bにO（logN）時間が得られます。新しい要素を追加するときは新しいノードへのポインタをキューにプッシュし、最も古い要素を削除するときはキューフロントが指すノードを削除する必要があります（もちろんキューからポップします）。
私は最も古いもので彼は挿入時間を意味し、最も大きい要素が最も高い値を持つ要素だと思います。多分あなたはそれが（値、挿入時間）のタペルとして書くことができます
値の最大ヒープにすべての要素を挿入し、最小で挿入時間を聞いてそれらを接続できる場合があります。私の頭の中には、接続されている2つのヒープがあり、ペアはタペルの表現です。本当にエレガントではありませんが、機能するはずです。挿入および削除するたびに、ヒーププロパティを確認する必要があります。