Prioritetskö
Wikipedia
En prioritetskö är en datastruktur för att lagra och hämta data.
Till varje element i prioritetskön finns ett prioriteringsvärde, detta kan utgöra ett bestämt kö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å opearationer. Den ena operationen lägger till ett element i prioritetskön. Den andra operationen plockar ut det element som har lägst prioritetsvärde (man skulle även kunna tänka sig det som har högst prioritetsvärde om det känns mer intuitivt).
Vanligtvis har man även andra operationer, den vanligaste är förmodligen en som visar det element som har lägst prioritetsvärde utan att avlägsna det.
[redigera] 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).
[redigera] Användningsområden
Prioritetsköer används på flera håll inom datavetenskapen bland annat i dijkstra's algoritm och kruskal's algoritm.
