Gibt es eine Prioritätswarteschlange mit

Es gibt sehr viele Datenstrukturen, die die Priority-Queue-Schnittstelle implementieren:

• Einfügen: Fügt ein Element in die Struktur ein
• Get-Min: Gibt das kleinste Element in der Struktur zurück
• Extract-Min: Entfernt das kleinste Element in der Struktur

Übliche Datenstrukturen, die diese Schnittstelle implementieren, sind (min) Heaps .

Normalerweise betragen die (amortisierten) Laufzeiten dieser Vorgänge:

• Einfügen: (manchmal O ( log n ) )$\mathcal{O}(1)$$\mathcal{O}(\log n)$
• Get-Min: $\mathcal{O}(1)$
• Extrakt-Min: $\mathcal{O}(\log n)$

Der Fibonacci-Heap erreicht beispielsweise diese Laufzeiten. Nun ist meine Frage die folgende:

Gibt es eine Datenstruktur mit folgenden (amortisierten) Laufzeiten?

• Einfügen: $\mathcal{O}(\log n)$
• Get-Min: $\mathcal{O}(1)$
• Auszug-Min: $\mathcal{O}(1)$

Wenn wir bei sortierter Eingabe eine solche Struktur in -Zeit aufbauen können, können wir zum Beispiel Linienschnittpunkte auf vorsortierten Eingaben mit o ( $\mathcal{O}(n)$Kreuzungen sind strikt schneller als wenn wir die 'üblichen' Prioritätswarteschlangen verwenden.$o\left(\frac{n}{\log n}\right)$

Unsere Idee ist es, mit Gewinde versehene Spreizbäume zu verwenden . Anders als im Wikipedia-Artikel werden wir die Bäume so fädeln, dass jeder Knoten einen Zeiger nextauf seinen Nachfolger in der Durchquerung in der richtigen Reihenfolge hat. Wir halten auch einen Zeiger startauf das kleinste Element im Baum.

Es ist leicht zu erkennen, dass das Extrahieren des kleinsten Elements in der (schlimmsten) Zeit : Folgen Sie einfach dem Zeiger, entfernen Sie das Minimum und ändern Sie den Zeiger auf das Minimum . Das Minimum kann niemals ein verlassenes Kind haben; Wenn es ein richtiges Kind hat, setzen wir es an die Stelle des Minimums im Baum. Wir führen nicht die Spreizoperation durch, die Spreizbäume normalerweise ausführen würden. Das Ergebnis ist ein noch recht ausgeglichener Suchbaum: Da wir nur die Knoten an der linken Flanke entfernen, wissen wir, dass bei einer Verringerung der Anzahl der Knoten (in einem betroffenen Teilbaum) aufgrund von Löschungen die Zahl (sub ) Die Höhe des Baumes wird um eins verringert.$\mathcal{O}(1)$startnext

Einfügungen sind in amortisierter Zeit möglich; Die Zick-Zack-Operationen (und was nicht) bringen auch hier den Baum wieder ins Gleichgewicht.$\mathcal{O}(\log n)$

Dies ist bestenfalls eine grobe Skizze. Dank geht an F. Weinberg, der mit mir und unserem Berater M. Nebel, der Spreizbäume erwähnte, über die einzige Baumvariante nachgedacht hat, die wir nicht ausprobiert hatten.

• Einfügen: $\mathcal{O}(\log n)$
• Get-Min: $\mathcal{O}(1)$
• Auszug-Min: $\mathcal{O}(1)$

Amortisierte Zeit

$cn \log n$$O(\log n)$$O(\log n)$$\Omega(\log n)$$O(1)$

Schlimmsten Fall

Sie können eine vorhandene Datenstruktur in der Literatur verwenden: Finger-Suchbäume, und einfach einen Zeiger auf das minimale Element verwalten. Sehen Sie diese Umfrage für einen Überblick, und das 1988 Papier von Levcopoulos und Overmars für eine umsetzbare Version , die Ihren Bedürfnissen entspricht.

$O(1)$$O(1)$

$O(1)$

$O(1)$

Auf Anfrage, hier ist die Struktur, die ich gefunden habe, nachdem ich die Frage formuliert habe:

Die Grundidee besteht darin, einen mit einem Thread versehenen Sündenbockbaum zusammen mit einem Zeiger auf das Minimum (und zum guten Teil auch auf das Maximum) zu verwenden. Eine einfachere Alternative zum Threading besteht darin, in jedem Knoten Vorgänger- und Nachfolgerzeiger zu verwalten (was äquivalent, einfacher, aber mit mehr Aufwand verbunden ist). Ich bin gekommen , es ist ein Sündenbock zu nennen Haufen , nur um es zu geben , einen Namen.

Gerade diese Grundstruktur gibt Ihnen diese Operationen:

• $\mathcal{O}(\log n)$
• $\mathcal{O}(\log n)$
• $\mathcal{O}(1)$
• Get-Min / Max: Gibt den Zeiger auf das Minimum oder Maximum zurück.

$\mathcal{O}(\log n)$$\mathcal{O}(1)$$\mathcal{O}(\log n)$$\mathcal{O}(1)$$\mathcal{O}(1)$$\mathcal{O}(1)$

• $\mathcal{O}(1)$

Dies kombinieren:

• $\mathcal{O}(1)$

Mit Zeigern können Sie ein bisschen mehr anfangen: Beispielsweise ist es nicht schwierig, einen Zeiger auf den Median oder eine andere Ordnungsstatistik zu pflegen, sodass Sie eine konstante Anzahl solcher Zeiger pflegen können, wenn Sie sie benötigen.

Einige andere Dinge:

• $n$$\mathcal{O}(n)$
• $\mathcal{O}(n)$

Und schließlich bin ich mir ziemlich sicher, dass Sie diese Operationen unterstützen können, aber ich muss ein bisschen mehr darüber nachdenken, bevor ich das sicher weiß:

• $\mathcal{O}(1)$

$\epsilon$$O(1)$$\log (1/\epsilon)$$\epsilon$

$\epsilon n$

Das originale, klare und gut geschriebene Papier finden Sie unter Bernard Chazelle, The Soft Heap: Eine Warteschlange mit ungefährer Priorität und optimaler Fehlerrate, Journal of the ACM, 47 (6), S. 1012-1027, 2000 . Eine alternative Implementierung und Analyse, die nach SODA'09 einfacher und intuitiver zu sein scheint, finden Sie in Kaplan H. & Zwick U., Eine einfachere Implementierung und Analyse von Chazelles weichen Haufen, 2009 .

Okay, endlich hast du die Komplexität, nach der du gesucht hast, und was am besten ist, fand ich in der Literatur:

Worst-Case-Komplexität

$\bf\mathcal{O}(1)$

$\bf\mathcal{O}(1)$

$\bf\mathcal{O}(1)$

$\bf\mathcal{O}(log\ n)$

Referenz

[3]$\mathcal{O}(1)$$\mathcal{O}(log\ n)$$\mathcal{O}(n)$

Brodal, Gerth Stølting. 'Fast Meldable Priority Queues'. In Proceedings of the 4th International Workshop zu Algorithmen und Datenstrukturen, 282–290. WADS '95. London, UK, UK: Springer-Verlag, 1995.

[3]: Dietz, Paul F und Rajeev Raman. 'Ein Finger-Suchbaum mit konstanter Aktualisierungszeit'. Informationsverarbeitungsbriefe 52, nr. 3 (1994): 147-154.

Dabei wird das RAM- Berechnungsmodell verwendet :

Unsere Datenstruktur verwendet das RAM-Modell (Random Access Machine) mit Maßeinheit und logarithmischer Wortgröße.

In jüngerer Zeit wurde ein Pointer-Machine- Modell einer Berechnungslösung vorgestellt [1].

[1]: Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis und Kostas Tsichlas. "Optimale Fingersuchbäume in der Zeigermaschine". J. Comput. Syst. Sci. 67, nein. 2 (September 2003): 381–418.

Annäherung an dieses Problem durch Beibehalten von zwei Datenstrukturen: einem Array und einem Binärbaum.

$\Omega(\dfrac{\log n}{\log\log n})$$\Omega(\log n)$

$\mathcal{O}(\log n)$$\mathcal{O}(\log n)$

null$\mathcal{O}(\log n)$

$\mathcal{O}(1)$$\mathcal{O}(1)$

$\mathcal{O}(\log n)$$\mathcal{O}(1)$delete_at(idx)

1 Patrascu, Mihai und Erik D. Demaine. "Logarithmische untere Grenzen im Zell-Sonden-Modell". SIAM J. Comput. 35, nein. 4 (April 2006): 932–963. doi: 10.1137 / S0097539705447256.

$O(1)$$O(\sqrt{log\text{ }log\text{ }n})$

Siehe Artikel 2007: Gleichwertigkeit zwischen Prioritätswarteschlangen und Sortieren nach Mikkel Thorup.

$O(n\text{ }\sqrt{log\text{ }log\text{ }n})$

Analyse

$\mathcal{o}(n\ log\ log\ n)$

$\mathcal{o}(log\ log\ n)$

$\mathcal{O}(1)$

$\mathcal{O}(n)$

$\mathcal{O}(1)$

$\mathcal{O}(1)$

Implementierung

1. $\mathcal{O}(1)$
2. $\mathcal{O}(6)$$\mathcal{O}(1)$
3. $k$$\pm$ $$((k > n_{\text{size}-1}) \lor (k<n_{0}) \lor ((k<n_{i}) \land (k>n_{i+1})))$$ $\mathcal{o}(log\ log\ n)$

[1]: Andersson, Arne und Christer Mattsson. 'Dynamische Interpolationssuche in O (log log n) Zeit'. In Automata, Languages ​​and Programming, herausgegeben von Andrzej Lingas, Rolf Karlsson und Svante Carlsson, 700: 15–27. Vorlesungsnotizen in der Informatik. Springer Berlin / Heidelberg, 1993. http://dx.doi.org/10.1007/3-540-56939-1_58 .