Kolejka liczb całkowitych priorytetowych z zależnym od dystrybucji deleteMin

Czy w kolejce liczb całkowitych priorytetowych, która używa słów spacji z następującymi operacjami, wszystko w najgorszym przypadku i bez dostępu do losowości:$O(n)$

• createEmptyQueuew dla pewnej stałej c .$O(lg^c U)$$c$
• insertw .$O(1)$
• deleteMin$O(\delta_{\min})$$\delta_{\min}$

Ponadto, gdy klucz zostanie poddany a , wszystkie dalsze wstawki mają .$k$deleteMin$> k$

Powiązana praca:

„Szybkie lokalne wyszukiwania i aktualizacje w ograniczonych wszechświatach” Bose et al. , Który jest szybszy niż potrzebuję, deleteMinale wolniejszy niż potrzebuję insert.

Brodnik i wsp. „Kolejka o stałym priorytecie w najgorszym przypadku” , która wykorzystuje egzotyczną „pamięć Yggdrasil”. Na potrzeby tego pytania interesują mnie bardziej standardowe modele liczb całkowitych RAM.

„Wieloprocesowa kolejka czasowa” Brodnika i Karlssona , która ogranicza wstawianie do elementów z kluczami w , gdzie jest wartością minimum klucz.$(k_{\min}, k_{\min} + \delta_{\min}]$$k_{\min}$

Zauważ, że jest to dość proste w przypadku tabeli skrótów, ale wykorzystuje ona amortyzację i losowość:

• Kolejki są parami tabeli skrótów kluczy i kopii klucza minimalnego.
• insert dodaje klucz do tabeli skrótów i aktualizuje minimalną kopię klucza, jeśli to konieczne.
• deleteMinsprawdza minimalny klucz w tabeli skrótów, a następnie wyszukuje następny minimalny klucz, wyszukując kolejno w kolejności.$k_{\min} + 1, k_{\min} +2, k_{\min} + 3, \dots$

W tym artykule [1] dodatkowo wprowadzono właściwość „palca czasu”, ujednoliconą właściwość obejmującą zarówno zestaw roboczy, jak i właściwości kolejki:

Prezentujemy kolejkę priorytetową, która obsługuje operacje: wstawianie w stałym czasie najgorszego przypadku i usuwanie, usuwanie-min, znajdowanie-min i klawisz zmniejszania na elemencie w najgorszym przypadku czas, w którym (odpowiednio ) to liczba elementów, do których uzyskano dostęp po (odpowiednio, przed) ostatnim dostępie i nadal znajdują się w kolejce priorytetowej w momencie wykonywania odpowiedniej operacji .$x$$O(lg(min\{w_x,q_x\}+2))$$w_x$$q_x$$x$

[1] A. Elmasry, A. Farzan i J. Iacono, „A Unifying Property for Distribution-Sensitive Priority Queues”, w Combinatorial Algorytmy, vol. 7056, C. Iliopoulos i W. Smyth, Eds. Springer Berlin Heidelberg, 2011, ss. 209–222.