Tidskompleksiteten ved at poppe (fjerne elementet med den højeste prioritet) fra en prioriteringskø afhænger af den underliggende implementering af den prioriterede kø. Her er en sammenbrud af fælles implementeringer:
* binær bunke:
* o (log n) . Dette er den mest almindelige og effektive implementering. Fjernelse af roden (højeste prioritetselement) tager O (1). Dog skal du derefter udskifte roden med det sidste element i dyngen og "heapify ned" for at gendanne heap -egenskaben. Denne heapify -operation tager o (log n) tid, hvor n er antallet af elementer i bunken.
* binært søgetræ (BST):
* o (log n) I det gennemsnitlige tilfælde for en afbalanceret BST (som et AVL-træ eller et rød-sort træ). At finde det maksimale (eller minimum, afhængigt af prioriteten) er O (log n), og at fjerne det er også O (log n).
* o (n) I værste tilfælde for en ubalanceret BST. Hvis træet er skævt (f.eks. Ligner en sammenkoblet liste), kan det tage lineær tid at finde og fjerne det maksimale/minimum.
* array eller linket liste (uordnet):
* o (n) . Du skal iterere gennem hele listen for at finde elementet med den højeste prioritet og derefter fjerne det.
* array eller linket liste (bestilt):
* Hvis der bestilles med prioritet (f.eks. Sorteret matrix):Popping af elementet med højeste prioritet (sandsynligvis i slutningen eller begyndelsen, afhængigt af bestillingen) kan være O (1). Men hvis du bruger en sorteret matrix og har brug for at opretholde den sorterede rækkefølge efter fjernelse af elementet, skal du muligvis skifte elementer, hvilket resulterer i O (n) i værste fald. Linkede lister kan undgå skiftet, så popping er O (1), hvis du ved, hvor det højeste prioriterede element er, men at finde det stadig var O (n) til at begynde med.
* fibonacci heap:
* o (log n) Amortiseret tid. Fibonacci-dynger er mere komplekse at implementere, men de tilbyder teoretisk bedre ydelse til visse operationer, især når du har mange 'faldende nøgle' operationer. "Amortiseret" betyder, at selvom individuelle operationer kan tage længere tid, er den gennemsnitlige tidskompleksitet over en række af operationer O (log N).
Sammendrag:
| Implementering | Tidskompleksitet (popping) |
| --------------------- | ----------------------- |
| Binær bunke | O (log n) |
| Afbalanceret BST | O (log n) |
| Ubalanceret BST | O (n) |
| Uordnet array/liste | O (n) |
| Bestilt array/liste | O (1) eller o (n) |
| Fibonacci heap | O (log n) (amortiseret) |
I praksis:
Den mest almindelige implementering af prioriterede køer er binær bunke på grund af dens gode ydelse (O (log n)) og relativt enkel implementering. Derfor kan du generelt antage, at tidskompleksiteten af at poppe fra en prioriteret kø skal være O (log n) Medmindre dokumentationen eller konteksten eksplicit specificerer en anden underliggende datastruktur.
