Prioritetskø

Prioritetskö, eller priority queue, är en abstrakt datastruktur som lagrar element tillsammans med en prioritet och möjliggör att element med högre prioritet tas bort först. Den följer inte nödvändigtvis ankomstordningen; ett högre prioritetsvärde tas alltid före lägre. Beroende av konvention kan man använda min-prioritet (lägsta numeriska prioritet är högsta) eller max-prioritet (högsta numeriska prioritet är högsta).

Grundläggande operationer inkluderar: Infoga(element, prioritet), topp/peek som returnerar elementet med högsta prioritet utan att ta bort det, Extrahera-min eller extrahera-max som tar bort och returnerar det elementet med högsta prioritet, ändra-prioritet (ändra prioriteten för ett befintligt element), samt isEmpty och size.

Den vanligaste implementationen är en binär heap (min-heap eller max-heap). Andra alternativ inkluderar binomial heap, Fibonacci heap, pairing heap och d-ary heap. Prestanda varierar beroende på konstruktion: i en binär heap är infoga och extrahera-min vanligtvis O(log n), medan ändra-prioritet ofta är O(log n). Vissa avancerade strukturer erbjuder amortiserad O(1) för ändring av prioritet och O(log n) för extrahering.

Användningsområden inkluderar kortaste vägen-algoritmer som Dijkstra och A*, händelsebaserad simulering samt CPU- eller nätverksschemaläggning där uppgifter prioriteras.

När det gäller lika prioter kan beteendet variera mellan implementationer; vissa prioritetsköer är stabila och bevarar insertionens ordning bland lika-prioritet, medan andra inte är det.