優先キューでO（1）の挿入と削除の両方を行うことはできますか？
優先キューはヒープを使用して実装でき、フィボナッチヒープの実行時間を見ると、削除ごとにO（logN）よりも優れた実行時間を取得することはできないようです。
N個のアイテムが与えられた場合、半分が最大優先度キューに、残り半分が最小優先度キューに含まれるデータ構造を実装しようとしています。次に、N個のアイテムすべてを順番に削除します。
N個すべての要素をO（N）時間で挿入できますが、N個すべてのアイテムを削除するにはO（N * logN）が必要なので、別のアプローチがより適切かどうか疑問に思います。
O（1）挿入とO（1）削除を使用して優先キューを作成できる場合は、それを使用して、O（n）時間でn個のアイテムのリストを並べ替えることができます。この回答で説明されているように、一般的なケースではO（n）で並べ替えることができないため、入力についてより多くの仮定を行わずに、O（1）の挿入とO（1）の削除で優先キューを構築することは不可能です。 。
たとえば、O（1）挿入とO（k）（kは挿入可能な最大要素）の削除を含む優先キューを作成できます。k個のリンクリストのテーブルを保持します。を挿入xすると、リストの先頭にアイテムが追加されxます。削除では、テーブルをスキャンして最初の空でないリストを見つける必要があります（次に、リストの最初の項目を削除して、そのリストのインデックスを返します）。リストはk個しかないため、削除にはO（k）時間がかかります。kが定数の場合、それはO（1）の除去になります。
実際には、カウントのテーブルを使用するとうまくいくでしょう。可変長整数のインクリメントは、償却分析を使用しない限り一定時間ではありませんが（これが、前の段落で使用しなかった理由です）、実際には、可変長のカウントは必要ありません。また、実際には、kが定数であっても、kが大きい場合は問題があります。メモリがすぐに不足し、最初のゼロ以外の要素のスキャンに時間がかかる場合があります。