Tidskompleksiteten af ​​almindelige operationer på en 'prioritetsqueue' i Java afhænger af den specifikke operation. Her er en sammenbrud:

* `Tilføj (e)` / `tilbud (e e)` (indsættelse): O (log n) - Dette skyldes, at den prioriterede kø skal opretholde sin bunkeegenskab, som kræver signing af det nye element op eller ned ad bunken.

* `Fjern ()` / `Poll ()` (Fjernelse af det højeste prioriterede element): O (log n) - Fjernelse af rodelementet (højeste prioritet) nødvendiggør udskiftning af det med det sidste element og derefter sigte udskiftningselementet ned ad bunken for at gendanne dyngen.

* `peek ()` (adgang til det højeste prioriterede element): O (1) - PEECHING AT HØJESTE PRIORITET Element (roden af ​​dyngen) er en direkte adgangsoperation.

* `indeholder (objekt o)`: O (n) - Dette kræver iterering gennem elementerne i køen for at kontrollere for lighed. Priorityqueues i Java giver ikke en effektiv måde at kontrollere for indeslutning på.

* `Fjern (objekt o)`: O (n) - I lighed med `Indeholder ()` indebærer dette iterering gennem elementerne for at finde og fjerne det specificerede objekt. Efter fjernelse af objektet skal heap -egenskaben opretholdes, som i værste fald kan tage O (n) tid. (Fjernelse af et vilkårligt element er ikke en standardprioritetskødrift, og ydelsen afspejler dette.)

* `størrelse ()`: O (1) - Størrelsen opretholdes som en medlemsvariabel, så adgang til det er en konstant tidsoperation.

* `isEmpty ()`: O (1) - Kontroller blot, om størrelsen er 0.

* `klar ()`: O (n) - fjerner alle elementer fra køen. Mens individuel fjernelse af element kan tage O (log n), tager det at rydde hele køen O (n). I nogle implementeringer kan dette faktisk implementeres som O (1) ved blot at nulstille det interne array og størrelse.

* `iterator ()`: O (1) - Returnerer en iterator i prioritetskøen. Iteratoren i sig selv er * ikke * bestilt, og iterering gennem elementerne vil være O (n).

Vigtige overvejelser:

* `PriorityQueue 'implementeres som en binær bunke. Heap -datastrukturen er det, der giver den sin logaritmiske ydelse til indsættelse og fjernelse af det højeste prioriterede element.

* komparatoren er afgørende. Sammenligneren (eller den naturlige rækkefølge af elementerne, hvis der ikke gives nogen komparator) er det, der bestemmer elementernes prioritet. Sammenlignerens 'sammenligne ()' -metoden skal være effektiv (typisk O (1)) for den samlede prioriterede køoperationer for at opretholde deres angivne kompleksitet.

* Fjernelse af vilkårlige elementer (`Fjern (objekt O)`) er ineffektivt. Hvis du ofte har brug for at fjerne vilkårlige elementer fra en prioriteret kø, skal du overveje at bruge en anden datastruktur eller en kombination af datastrukturer (f.eks. Et `Treeset` kombineret med en` hashmap 'til at spore elementpositioner). Standardprioritetskøer er optimeret for effektiv adgang til det højeste prioriterede element.

Kortfattet:

De vigtigste operationer for `tilføj ()` og `Fjern ()` (af det * højeste * prioriterede element) er O (log n), hvilket gør `prioritetQueue 'et meget effektivt valg for scenarier, hvor du har brug for at opretholde en sorteret samling og gentagne gange få adgang til eller fjerne minimumet (eller maksimum, afhængigt af dit sammenligningselement).