Prioritetskö
 |
Den här artikeln behöver källhänvisningar för att kunna verifieras. (2017-08) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan. |
En prioritetskö är en abstrakt datatyp för att lagra och hämta data. Skillnaden mot en vanlig kö är att när man plockar ut ett element ur kön får man alltid ut det med lägst/högst prioritet, oavsett i vilken ordning elementen lagts in.
Till varje element i prioritetskön finns ett prioriteringsvärde, detta kan utgöra ett bestämt nummer eller kan det avgöras av elementens inbördes ordning givet av någon jämförelsefunktion. Om man exempelvis lagrar namn i prioritetskön skulle elementen kunna ges prioritetsvärden efter deras alfabetiska ordning.
På en prioritetskö måste man kunna utföra minst två operationer:
- Lägga till ett element i prioritetskön samt eventuellt ange dess prioritetsvärde
- Plocka ut det element som har lägst (alternativt högst) prioritetsvärde
Vanligtvis har man även andra operationer, den vanligaste är en som returnerar det element som har lägst/högst prioritetsvärde utan att avlägsna det från kön.
Implementation
[redigera | redigera wikitext]En prioritetskö implementeras vanligtvis med hjälp av ett partiellt-ordnat vänsterbalanserat binärt träd (även kallat heap) där varje barn har högre prioritetsvärde än sin förälder; detta ger tidskomplexitet O(log(n)) för de båda standard-operationerna.
Man kan även med enkelhet implementera ena operationen i O(n) och andra i O(1), dock är det bevisat att man inte kan implementera båda i O(1).[källa behövs]
Användningsområden
[redigera | redigera wikitext]Prioritetsköer används på flera håll inom datavetenskapen bland annat i Dijkstras algoritm och Kruskals algoritm.