Prioriteettijärjestysalgoritmin

Prioriteettijärjestysalgoritmi, tunnetaan myös nimellä priority queue algorithm, on abstrakti tietorakenne, joka hallitsee kokoelmaa alkioita, joista jokaisella on määritetty prioriteetti. Algoritmin päätehtävä on mahdollistaa alkioiden tehokas poistaminen kokoelmasta sen korkeimman tai alhaisimman prioriteetin omaavan alkion perusteella. Tämä on hyödyllistä monissa tietojenkäsittelytehtävissä, joissa tiettyjen kohteiden käsittely on tärkeämpää kuin toisten.

Yleisimpiä toteutuksia prioriteettijärjestysalgoritmille ovat keko (heap) ja järjestetty taulukko. Kekopohjaiset toteutukset tarjoavat tyypillisesti O(log n) aikakompleksisuuden lisäys- ja poisto-operaatioille, missä n on alkioiden määrä. Järjestetyt taulukot voivat tarjota nopeamman alkioiden haun, mutta niiden lisäys- ja poisto-operaatiot voivat olla hitaampia.

Prioriteettijärjestysalgoritmeja käytetään laajalti monissa sovelluksissa. Niitä hyödynnetään esimerkiksi resurssienhallinnassa käyttöjärjestelmissä, jossa prosessien prioriteetit määräävät niiden suoritusjärjestyksen. Dijkstra-algoritmissa, joka löytää lyhimmän polun graafissa, prioriteettijonoa käytetään seuraavan vierailtavan solmun valitsemiseen tehokkaasti. Lisäksi niitä käytetään tiedonpakkausalgoritmeissa ja simulaatiojärjestelmissä.