Tidskomplexiteten för poppning (ta bort elementet med högsta prioritet) från en prioriterad kö beror på den underliggande implementeringen av prioriteringskön. Här är en uppdelning av vanliga implementeringar:
* binär hög:
* o (log n) . Detta är den vanligaste och effektiva implementeringen. Att ta bort roten (högsta prioritetselement) tar O (1). Men du måste sedan ersätta roten med det sista elementet i högen och "heapify down" för att återställa högegenskapen. Denna heapify -operation tar o (log n) tid, där n är antalet element i högen.
* binärt sökträd (BST):
* o (log n) I det genomsnittliga fallet för en balanserad BST (som ett AVL-träd eller ett rött svart träd). Att hitta det maximala (eller minimum, beroende på prioritering) är O (log N), och att ta bort den är också O (log N).
* o (n) I värsta fall för en obalanserad BST. Om trädet är skevat (t.ex. liknar en länkad lista) kan det ta linjär tid att hitta och ta bort det maximala/minimum.
* array eller länkad lista (oordnad):
* o (n) . Du måste iterera genom hela listan för att hitta elementet med högsta prioritet och sedan ta bort det.
* array eller länkad lista (beställd):
* Om det beställs efter prioritet (t.ex. sorterad matris):Poppning av elementet med högsta prioritet (troligen i slutet eller början, beroende på beställningen) kan vara O (1). Men om du använder en sorterad matris och behöver behålla den sorterade ordningen efter att du har tagit bort elementet, kan du behöva flytta element, vilket resulterar i O (n) i värsta fall. Länkade listor kan undvika växlingen, så popping är o (1) om du vet var det högsta prioritetselementet är, men att hitta det var fortfarande o (n) till att börja med.
* Fibonacci Heap:
* o (log n) amorterad tid. Fibonacci-högar är mer komplexa att implementera, men de erbjuder teoretiskt bättre prestanda för vissa operationer, särskilt när du har många "minskande nyckeloperationer. "Amorterad" betyder att även om enskilda operationer kan ta längre tid, är den genomsnittliga tidskomplexiteten över en sekvens av operationer O (log N).
Sammanfattning:
| Implementering | Tidskomplexitet (popping) |
| --------------------- | ----------------------- |
| Binär hög | O (log n) |
| Balanserad BST | O (log n) |
| Obalanserad BST | O (n) |
| Oordnad matris/lista | O (n) |
| Beställd matris/lista | O (1) eller o (n) |
| Fibonacci Heap | O (log n) (amorterad) |
I praktiken:
Den vanligaste implementeringen för prioriterade köer är den binära högen på grund av dess goda prestanda (O (log N)) och relativt enkel implementering. Därför kan du i allmänhet anta tidskomplexiteten för att poppa från en prioriterad kö för att vara o (log n) Om inte dokumentationen eller sammanhanget uttryckligen anger en annan underliggande datastruktur.
