prioriteettijono

Prioriteettijono on tietorakenne, joka tallentaa alkioita jokaiselle prioriteetille ja mahdollistaa korkean (tai matalimman) prioriteetin omaavan alkion nopean hakemisen. Jokaisella tallennetulla alkiolla on prioriteetti, jonka perusteella jono järjestetään. Tavoitteena on tarjota nopea pääsy siihen alkiolle, jolla on suurin tai pienin prioriteetti.

Operaatioita ovat muun muassa insert (uosuutta uusi alkio jonoon), extract-min tai extract-max (poistaa ja palauttaa alkion, jolla on korkein tai matalin prioriteetti) sekä peek tai top (palauttaa ilman poistamista tämänhetkisen kärjessä olevan alkion). Monimutkaisuuksien osalta perinteinen min-heap tai max-heap tarjoaa insert- ja remove-toiminnoille O(log n) ajassa. Decrease-key- ja delete-operatiot voivat olla toteutettavissa tehokkaasti eri tavalla, mikä vaikuttaa kokonaisuuden suorituskykyyn.

Toteutukset ja rakenteet: yleisin toteutus on binäärinen heap, jossa jono säilyttää kehyksen, jossa vanhempi solmu on pienempi (tai suurempi) kuin sen lapsi. Muita toteutuksia ovat binomial heap, Fibonacci heap ja pairing heap; niissä on erilaisia taka-ajoja dekrementointi- tai poistolippujen suhteen, ja ne voivat tarjota parempia amortisoituja aikavaikutuksia tietyissä käyttötapauksissa.

Ominaisuuksia: prioriteettijonot eivät yleensä ole vakaita, mikä tarkoittaa, että samoilla prioriteeteilla olevat alkiot voivat poistua eri järjestyksessä. Tie-breakereita käytetään joskus, esimerkiksi lisäamalla järjestysnumero alkioihin, jotta järjestys säilyy tietyn toisen kriteerin mukaan.

Sovelluksia: tehtävien ajoitus, tapahtumien käsittely simulaatioissa, sekä graafialgoritmit kuten Dijkstra ja Prim, missä tärkeimmän tapahtuman löytäminen on kriittistä. Useimmat ohjelmointikielet tarjoavat valmiita toteutuksia tai kirjastoja Prioriteettijonoille.