Die zeitliche Komplexität des Knalls (das Element mit der höchsten Priorität) aus einer Prioritätswarteschlange hängt von der zugrunde liegenden Implementierung der vorrangigen Warteschlange ab. Hier ist eine Aufschlüsselung gemeinsamer Implementierungen:
* Binärhaufen:
* o (log n) . Dies ist die häufigste und effizienteste Implementierung. Das Entfernen des Wurzels (höchstes Prioritätselement) erfordert O (1). Anschließend müssen Sie das Wurzel jedoch durch das letzte Element im Haufen ersetzen und nach unten "häufen", um die Heap -Eigenschaft wiederherzustellen. Dieser Heapify -Operation benötigt die Zeit von O (log n), wobei n die Anzahl der Elemente im Haufen ist.
* Binärer Suchbaum (BST):
* o (log n) in dem durchschnittlichen Fall für einen ausgewogenen BST (wie ein AVL-Baum oder einen rot-schwarzen Baum). Das Finden des Maximums (oder Minimums, abhängig von der Priorität) ist o (log n), und das Entfernen von Os ist auch o (log n).
* o (n) im schlimmsten Fall für eine unausgeglichene BST. Wenn der Baum verzerrt ist (z. B. ähnelt einer verknüpften Liste), kann das Finden und Entfernen des Maximums/Minimums die lineare Zeit in Anspruch nehmen.
* Array oder verknüpfte Liste (nicht ordnungsgemäß):
* o (n) . Sie müssen die gesamte Liste durchlaufen, um das Element mit höchster Priorität zu finden und es dann zu entfernen.
* Array oder verknüpfte Liste (bestellt):
* Wenn Sie nach Priorität bestellt (z. B. sortiertes Array):Das Element mit höchster Priorität (wahrscheinlich am Ende oder Anfang, abhängig von der Bestellung), kann o (1) sein. Wenn Sie jedoch ein sortiertes Array verwenden und die sortierte Reihenfolge nach dem Entfernen des Elements beibehalten müssen, müssen Sie möglicherweise Elemente verschieben, was zu O (n) im schlimmsten Fall führt. Verbindete Listen können das Verschieben vermeiden, so dass das Knallen o (1) ist, wenn Sie wissen, wo sich das Element mit höchster Priorität befindet, aber es war immer noch o (n) zu finden.
* Fibonacci Heap:
* o (log n) amortisierte Zeit. Fibonacci-Haufen sind komplexer zu implementieren, bieten jedoch theoretisch eine bessere Leistung für bestimmte Operationen, insbesondere wenn Sie viele Abläufe haben. "Amortisiert" bedeutet, dass die einzelnen Operationen zwar länger dauern können, die durchschnittliche Zeitkomplexität über eine Abfolge von Operationen o (log n) ist.
Zusammenfassung:
| Implementierung | Zeitkomplexität (Knallen) |
| --------------------- | ----------------------- |
| Binärhaufen | O (log n) |
| Ausgeglichener Bst | O (log n) |
| Ungewechseltes Bst | O (n) |
| Ungeordnetes Array/List | O (n) |
| Bestellte Array/Liste | O (1) oder o (n) |
| Fibonacci Heap | O (log n) (amortisiert) |
in der Praxis:
Die häufigste Implementierung für vorrangige Warteschlangen ist der binäre Haufen , aufgrund seiner guten Leistung (O (log n)) und relativ einfacher Implementierung. Daher können Sie im Allgemeinen die zeitliche Komplexität des Ausschreitens einer vorrangigen Warteschlange für o (log n) übernehmen Es sei denn, die Dokumentation oder der Kontext gibt explizit eine andere zugrunde liegende Datenstruktur an.
