Tidskomplexiteten för gemensamma operationer på en "prioriteradQueue" i Java beror på den specifika operationen. Här är en uppdelning:
* `lägg till (e e)` / `erbjudande (e e)` (insättning): O (log n) - Detta beror på att prioriteringskön måste behålla sin högegenskap, som kräver att det nya elementet siktar upp eller ner.
* `ta bort ()` / `poll ()` (borttagning av det högsta prioritetselementet): O (log n) - Att ta bort rotelementet (högsta prioritet) kräver att det ersätter det med det sista elementet och sedan siktar ersättningselementet ner i högen för att återställa högegenskapen.
* `peek ()` (åtkomst till det högsta prioritetselementet): O (1) - Peeking vid det högsta prioritetselementet (The Roep of the Heap) är en direktåtkomstoperation.
* `innehåller (objekt o)`: O (n) - Detta kräver iterering genom elementen i kön för att kontrollera om jämlikhet. Prioriterade Questues i Java ger inte ett effektivt sätt att kontrollera om det är inneslutning.
* `ta bort (objekt o)`: O (n) - I likhet med `innehåller ()`, innebär detta att iterera genom elementen för att hitta och ta bort det angivna objektet. Efter att ha tagit bort objektet måste högegenskapen upprätthållas, vilket i värsta fall kan ta o (n) tid. (Att ta bort ett godtyckligt element är inte en standardprioritetsköoperation, och prestanda återspeglar detta.)
* `storlek ()`: O (1) - Storleken upprätthålls som en medlemsvariabel, så åtkomst till den är en konstant tidsoperation.
* `isEmpty ()`: O (1) - Kontrollerar helt enkelt om storleken är 0.
* `klar ()`: O (n) - tar bort alla element från kön. Medan individuellt elementborttagning kan ta O (log n) tar rensning av hela köen o (n). I vissa implementeringar kan detta faktiskt implementeras som O (1) genom att bara återställa den interna matrisen och storleken.
* `iterator ()`: O (1) - Returnerar en iterator för prioriteringskön. Iteratoren själv är * inte * beställd, och iterering genom elementen kommer att vara o (n).
Viktiga överväganden:
* `Priorityqueue` implementeras som en binär hög. HEAP -datastrukturen är det som ger den sin logaritmiska prestanda för införande och borttagning av det högsta prioriterade elementet.
* komparatorn är avgörande. Comparatorn (eller den naturliga beställningen av elementen om ingen komparator tillhandahålls) är det som bestämmer elementens prioritering. Comparators metod "jämför ()" måste vara effektiv (vanligtvis O (1)) för den övergripande prioriterade köoperationerna för att upprätthålla sin angivna komplexitet.
* Ta bort godtyckliga element (`ta bort (objekt o)`) är ineffektivt. Om du ofta behöver ta bort godtyckliga element från en prioriterad kö kan du överväga att använda en annan datastruktur eller en kombination av datastrukturer (t.ex. en "Treeset" i kombination med en "hashmap" för att spåra elementpositioner). Standardprioritetsköer är optimerade för effektiv tillgång till det högsta prioritetselementet.
Sammanfattningsvis:
De viktigaste operationerna för `add ()` och `ta bort ()` (av * högsta * prioriterade elementet) är o (log n), vilket gör `priorityqueue 'till ett mycket effektivt val för scenarier där du behöver för att upprätthålla en sorterad samling och upprepade gånger åtkomst eller ta bort det minsta (eller maximala, beroende på ditt jämförande) element.
