Prioritetskö

En prioritetskö är en abstrakt datatyp för att lagra och hämta data. Skillnaden mot en vanlig ä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

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

Prioritetsköer används på flera håll inom datavetenskapen bland annat i Dijkstras algoritm och Kruskals algoritm.

Se även

Media som används på denna webbplats

Question book-4.svg
Författare/Upphovsman: Tkgd2007, Licens: CC BY-SA 3.0
A new incarnation of Image:Question_book-3.svg, which was uploaded by user AzaToth. This file is available on the English version of Wikipedia under the filename en:Image:Question book-new.svg