In Python bietet das heapq -Modul eine Prioritätswarteschlange.
Es hat Methoden zum Einfügen und Poppen von Elementen.
Wie entfernen Sie ein eingefügtes Element mit der niedrigsten Priorität aus der Warteschlange?
(Alternative Rezepte, die dies unter Verwendung alternativer anderer Sammlungen tun, sind ebenfalls willkommen)
Das Modul heapq verwendet Standard-Python-Listen als zugrunde liegende Datenstruktur. Sie können danach einfach die standardmäßige list -Methode remove() und heapify() erneut verwenden. Beachten Sie, dass dies jedoch lineare Zeit benötigt.
Sie können die Leistung des Heap-Vorgangs mithilfe der undokumentierten Funktion heapify._siftup() verbessern, aber der gesamte Prozess ist immer noch O (n), da list.remove() O (n) ist.
Wenn Sie den Speicherort des Elements kennen, das Sie entfernen möchten, können Sie Folgendes tun:
%Vor%Der erste Schritt ist jetzt O (1) Zeit, und der zweite Schritt kann O (log (N)) gemacht werden, indem die undokumentierten Daten verwendet werden. Natürlich ist es immer noch O (N), k zu finden, wenn Sie es nicht schon haben.
Es gibt eine Datenstruktur namens treap , die eine Kombination aus Warteschlange und Binärbaum darstellt. (Baum-Haufen). Es ermöglicht Log-n-Suche, die Ihnen helfen könnte.
Es gibt eine Python-Treap-Implementierung auf PyPi ..;)
Tags und Links python data-structures