Max in O (1) löschen und in O (logn) einfügen

Ihre Anforderungen sind sehr spezifisch - Sie interessieren sich nur für diese beiden Operationen: Fügen Sie O (lg n ) und deleteMin O ein (1).

Keine der bekannten Heap-Strukturen erfüllt Ihre spezifischen Einschränkungen. Stattdessen ist die beste Struktur (wenn auch theoretisch - galaktische Strukturen , wie manche sie nennen würden) die Brodal-Warteschlange , die alle Heap-Operationen in O (1) Worst-Case-Zeit durchführt , außer deleteMin, die immer noch die Zeit des schlechtesten Falls O (lg n ) einnimmt. Alle anderen bekannten Strukturen sind nicht besser.

Da Sie nur an diesen beiden Vorgängen interessiert sind, können Sie möglicherweise mit einer benutzerdefinierten Struktur arbeiten, die nur diese beiden Vorgänge gut beherrscht, da Sie sich nicht um Save-Key, Merge usw. kümmern müssen .. dass allgemeinere Heap-Strukturen sich Sorgen machen müssen.

Aufrechterhalten einer dualen Struktur, DL , die Folgendes enthält:

1. Sortiertes dynamisches Array , D , für das Sie eine Suche in O (lg n ) Zeit durch binäre Suche.
2. Sortierte verkettete Liste L , aus der Sie eine deleteMin-Instanz in O (1) und eine Einfügung mit einer Nachfolger- (oder Vorgänger-) Referenz in O (1) Worst-Case-Zeit.
3. Sortierte Liste T von Elementen, die kürzlich in L eingefügt, aber noch nicht mit D synchronisiert wurden.

Halten Sie außerdem eine Verknüpfung zwischen jedem Eintrag in L und seinem entsprechenden Eintrag in D oder T und umgekehrt. Außerdem müssen Sie für jeden Eintrag von D ein Bit angeben, das angibt, ob es in L gelöscht wurde oder nicht. Um später eine Massensynchronisation zwischen D und L durchzuführen, möchten Sie vielleicht auch die Anzahl der Löschungen, d , verfolgen L seit der letzten Synchronisierung. Sie können eine Synchronisierung nach der folgenden Invariante durchführen:

• Invariante 1: d + | T | & lt; n

wird verletzt. Auf diese Weise bleibt die Synchronisationszeit in n linear und Sie können immer | T | garantieren und d liegen innerhalb überschaubarer Grenzen.

Um also ein neues Element e in DL einzufügen, führen Sie zuerst eine Suche ( e ) in D für seinen Nachfolger (Vorgänger) und eine andere Suche nach seinem Nachfolger in T und greifen Sie die Referenz des größeren Nachfolgers (kleinerer Vorgänger) und verwenden Sie das, um eine Einfügung in L und e zu T hinzufügen und Referenzen pflegen. Nach dem Einfügen von e überprüfen wir, ob die Invariante 1 verletzt ist. Wenn dies der Fall ist, lösen wir eine Synchronisierung aus.

Eine Synchronisation führt im Wesentlichen den Inhalt von T und D zusammen, während Elemente, die als gelöscht markiert sind, in eine neue D Struktur entfernt werden. Dies kann zeitlich linear in | T | erfolgen + | D | = O (n). In einer anderen linearen Zeit können Referenzen zwischen L und D aktualisiert werden. Die Kosten dieser Massensynchronisation können über die Einfügungen und Löschungen verteilt (amortisiert) werden. Aus diesem Grund sind diese Kosten nur amortisierte Kosten.

Um deleteMin zu verwenden, löschen Sie einfach den Kopf von L und verwenden den Rückwärtslink zu D , um den entsprechenden Eintrag in D zu markieren gelöscht und inkrementiert d .

Beobachtung 1 : Beachten Sie, dass deleteMin immer das minimale Element löscht, da L immer auf dem neuesten Stand ist.

Beobachtung 2 : D stimmt nicht immer mit L überein. Es könnte einige gelöschte Elemente (so markiert) und einige eingefügte Elemente nur im T haben.

Nach Observation 2 müssen wir zu einem bestimmten Zeitpunkt eine Synchronisation von D mit L planen, um das O zu erhalten (lg n ) Kosten finden und einfügen. Dies geschieht immer dann, wenn Invariante 1 verletzt wird.

Ein nervtötendes Problem, über das ich schon einmal gesprochen habe, ist folgendes: Wie fügt man in T in logarithmischer Zeit ein, während man während der Synchronisation immer noch einen linearen Scan durchführen kann. Nur ein ausgewogener Baum kann dies erreichen. Ich hatte ein bisschen mit der Idee gespielt, die Größe von T auf logarithmische Größe zu beschränken, aber das würde die amortisierten Kosten der Synchronisierung erhöhen, wenn genug Anzahl von Einfügungen zum Auslösen einer Synchronisierung erfolgt. Es scheint so, als ob hier eine Art Thread-Balanced-Tree oder sogar eine Skip-Liste helfen würde.

Fühlen Sie sich frei, Kritik zu üben und Verbesserungen vorzuschlagen, da ich hier nicht alle Behauptungen bewiesen oder umgesetzt habe.

Update : Wie von @ delnan aufgezeigt, werden diese Kosten amortisiert. Ich habe die Beschreibung aktualisiert, um diese Tatsache hervorzuheben und zur Klarheit überarbeitet. Vielleicht kann die Amortisation mit ein paar Tricks entfernt werden, aber wir werden in diesem Fall mit einer anderen galaktischen Struktur enden.

Ich schlage vor, dass Sie eine Skip-Liste verwenden, da es die am einfachsten zu implementierende Datenstruktur ist, die ich mir vorstellen kann diese Operationen mit der geforderten Komplexität. Fibonacci-Heap wird auch die Aufgabe erledigen, aber es ist wahrscheinlich schwieriger zu implementieren.

EDIT: Ich nehme mein Wort zurück für den Fibonacci-Heap - es unterstützt konstante Einfügung und O(log(n)) delete_min, was das Gegenteil von dem ist, was Sie wollen. Entschuldigung dafür.