* Binaire heap:

* O(log n) . Dit is de meest voorkomende en efficiënte implementatie. Voor het verwijderen van de root (element met de hoogste prioriteit) is O(1) nodig. U moet dan echter de root vervangen door het laatste element in de heap en "heapify down" om de heap-eigenschap te herstellen. Deze heapify-bewerking kost O(log n) tijd, waarbij n het aantal elementen in de heap is.

* Binaire zoekboom (BST):

* O(log n) in het gemiddelde geval voor een gebalanceerde BST (zoals een AVL-boom of een rood-zwarte boom). Het vinden van het maximum (of minimum, afhankelijk van de prioriteit) is O(log n), en het verwijderen ervan is ook O(log n).

* O(n) in het ergste geval voor een onevenwichtige BST. Als de boom scheef staat (bijvoorbeeld lijkt op een gekoppelde lijst), kan het vinden en verwijderen van het maximum/minimum lineaire tijd in beslag nemen.

* Array of gekoppelde lijst (ongeordend):

* O(n) . U moet de hele lijst doorlopen om het element met de hoogste prioriteit te vinden en dit vervolgens te verwijderen.

* Array of gekoppelde lijst (geordend):

* Indien geordend op prioriteit (bijvoorbeeld gesorteerde array):Het element met de hoogste prioriteit (waarschijnlijk aan het einde of begin, afhankelijk van de volgorde) kan O(1) zijn. Als u echter een gesorteerde array gebruikt en de gesorteerde volgorde moet behouden nadat u het element hebt verwijderd, moet u mogelijk elementen verschuiven, wat in het ergste geval resulteert in O(n). Gekoppelde lijsten kunnen het verschuiven vermijden, dus knallen is O(1) als je weet waar het element met de hoogste prioriteit is, maar ontdekt dat het in het begin nog steeds O(n) was.

* Fibonacci-hoop:

* O(log n) afgeschreven tijd. Fibonacci-heaps zijn complexer om te implementeren, maar ze bieden theoretisch betere prestaties voor bepaalde bewerkingen, vooral als je veel 'verlaag-sleutel'-bewerkingen hebt. 'Geamortiseerd' betekent dat, hoewel individuele bewerkingen langer kunnen duren, de gemiddelde tijdscomplexiteit over een reeks bewerkingen O(log n) bedraagt.

Samenvatting:

| Implementatie | Tijdcomplexiteit (knallen) |

| -------------------- | ---------------------- |

| Binaire heap | O(logboek n) |

| Evenwichtige BST | O(logboek n) |

| Onevenwichtige BST | O(n) |

| Ongeordende array/lijst | O(n) |

| Bestelde array/lijst | O(1) of O(n) |

| Fibonacci-hoop | O(log n) (afgeschreven) |

In de praktijk:

De meest gebruikelijke implementatie voor prioriteitswachtrijen is de binaire heap , vanwege de goede prestaties (O(log n)) en relatief eenvoudige implementatie. Daarom kun je er in het algemeen van uitgaan dat de tijdscomplexiteit van het uit een prioriteitswachtrij springen O(log n) is. tenzij de documentatie of context expliciet een andere onderliggende datastructuur specificeert.