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が大きい場合は問題があります。メモリがすぐに不足し、最初のゼロ以外の要素のスキャンに時間がかかる場合があります。