Från Rilpedia

En prioritetskö är en datastruktur 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 så 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 så 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

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).

Användningsområden

Prioritetsköer används på flera håll inom datavetenskapen bland annat i dijkstra's algoritm och kruskal's algoritm.