Python: Element aus Heap löschen

Question

Python hat heapq Modul, das Heap-Datenstruktur implementiert und es unterstützt einige grundlegende Vorgänge (Push, Pop).

Wie entfernt man i-tes Element aus dem Heap in O (log n)? Ist es überhaupt möglich mit heapq oder muss ich ein anderes Modul verwenden?

Hinweis, es gibt ein Beispiel am Ende der Dokumentation: http://docs.python.org/library/heapq.html die einen möglichen Ansatz vorschlagen - das ist nicht, was ich will. Ich möchte das Element entfernen, nicht nur als entfernt markieren.

Answer 1

Sie können das i-te Element aus einem Haufen entfernen ganz einfach:

h[i] = h[-1] 
h.pop() 
heapq.heapify(h) 

einfach das Element, das Sie mit dem letzten Element entfernen möchten, ersetzen und das letzte Element entfernen Sie dann den Haufen wieder heapify. Das ist O (n), wenn Sie möchten, können Sie dasselbe in O tun (log (n)), aber Sie müssen einige der internen Heapify-Funktionen aufrufen, oder besser, wie larsmans darauf hingewiesen hat, kopieren Sie einfach die Quelle von _siftup/_siftdown aus heapq.py in Ihren eigenen Code:

h[i] = h[-1] 
h.pop() 
if i < len(h): 
    heapq._siftup(h, i) 
    heapq._siftdown(h, 0, i) 

Beachten Sie, dass Sie in jedem Fall nicht nur tun h[i] = h.pop() wie das wäre, wenn i Referenzen das letzte Element scheitern. Wenn Sie im Spezialfall das letzte Element entfernen, können Sie das Überschreiben und Pop kombinieren.

Beachten Sie, dass die typische Größe des Heap je finden Sie vielleicht, dass nur heapify Aufruf während theoretisch weniger effizient schneller sein könnte als die Wiederverwendung von _siftup/_siftdown: ein wenig Selbstbeobachtung wird zeigen, dass heapify wahrscheinlich in C implementiert ist, aber die C-Implementierung der internen Funktionen sind nicht offengelegt. Wenn Ihnen die Leistung wichtig ist, sollten Sie einige Zeittests an typischen Daten durchführen, um zu sehen, welche die beste ist. Wenn Sie nicht wirklich massive Haufen haben, ist Big-O vielleicht nicht der wichtigste Faktor.

Edit: jemand versucht, diese Antwort zu bearbeiten, den Anruf zu _siftdown mit einem Kommentar zu entfernen, dass:

_siftdown nicht benötigt wird. New h [i] ist garantiert das kleinste Kind der alten h [i], das immer noch größer ist als das Elternteil des alten h [i] (neues Elternteil von h [i]). _Settdown wird ein No-Op sein. Ich muss bearbeiten, da ich nicht genug rep haben, um einen Kommentar noch hinzuzufügen.

Was sie in diesem Kommentar verpasst haben, ist, dass h[-1] kein Kind von h[i] überhaupt sein könnte. Der neue Wert, der bei h[i] eingefügt wird, könnte von einem völlig anderen Zweig des Heaps kommen, so dass er in beide Richtungen gesiebt werden müsste.

auch auf den Kommentar zu fragen, warum gerade nicht sort() verwenden, um die Haufen wiederherzustellen: Aufruf _siftup und _siftdown sind beide O-Operationen (n log), heapify Aufruf ist O (n).Der Aufruf von sort() ist eine Operation O (n log n). Es ist durchaus möglich, dass Calling Sort schnell genug ist, aber für große Haufen ist es ein unnötiger Overhead.

Bearbeitet um das von @Seth Bruder aufgezeigte Problem zu vermeiden. Wenn i auf das Endelement verweist, würde der Aufruf _siftup() fehlschlagen, aber in diesem Fall bricht ein Element am Ende des Heapspeichers die Heap-Invariante nicht.

Answer 2

(a) Erwägen Sie, warum Sie nicht faul löschen möchten. In vielen Fällen ist es die richtige Lösung.

(b) Ein Heap ist eine Liste. Sie können ein Element wie jede andere Liste auch per Index löschen, müssen es dann aber erneut zusammenfassen, da es die Heap-Invariante nicht mehr erfüllt.