Prioriteettijono on abstrakti tietotyyppi, jolle on määritelty operaatiot 1) lisäys ja 2) prioriteetiltaan suurimman (tai pienimmän) alkion poisto.
Käytännön ongelma: Töidenjärjestelyongelma
Prioriteettijonossa pidetään yllä odottavia töitä ja niiden keskinäisiä prioriteetteja. Kun yksi työ tulee valmiiksi, valitaan seuraavaksi sellainen työ, jolla on korkein prioriteetti. Valittu työ poistetaan prioriteettijonosta. Lisäksi prioriteettijonoon voidaan kaiken aikaa lisätä uusia töitä. Lisäykset ja poistot voivat siis limittyä mielivaltaisesti ja silti rakenteen tulisi toimia tehokkaasti.
Binäärikeko
Binäärikeko (tai lyhyemmin keko; on muitakin kekorakenteita, mutta yleisesti ilman lisämääreitä keko-käsitteellä viitataan juuri binäärikekoon) on tärkeä prioriteettijonon toteutus. Keko on täydellinen binääripuu, jossa kaikki tasot mahdollisesti alimmaista lukuunottamatta ovat täynnä ja alimmaisella tasolla kaikki alkiot on sijoitettu vasempaan reunaan. Tällöin tietorakenne voidaan toteuttaa yksinkertaisena taulukkona. Jos keko on ns. minimikeko (MinHeap), kunkin solmun prioriteettiarvo on pienempi (tai yhtäsuuri) kuin sen lasten prioriteettiarvot. Tällöin sanotaan keolla olevan kekoehto "isä pienempi kuin lapsi". Kekoehto voi luonnollisesti olla myös toisin päin, jolloin kyseessä on maksimikeko (MaxHeap).
Kekoalgoritmit pohjautuvat yleisesti seuraavalle perusperiaatteelle. Tehdään ensin yksinkertainen paikallinen muutos. Sen jälkeen kekoa muokataan siten, että kekoehto on jälleen voimassa. Muutoksia tarvitsee tehdä vain yhdellä polulla, joka johtaa juuresta kohti lehtiä tai päin vastoin.
Keko lyhyesti
Kekoehto (maksimikeko): Isä suurempi kuin lapsensa
Kekoehto (minimikeko): Isä pienempi kuin lapsensa
This document was last updated 03.11.2011. Please send your comments to Mikko Laakso and Ari Korhonen.