Keko (tietorakenne)

Tämä artikkeli käsittelee tietorakennetta. Sitä tule sekoittaa ohjelman ajon aikana dynaamisesti hallitsemaan kekomuistiin.

Keko (engl. heap), joskus myös kasa^[1], on tietojenkäsittelytieteessä käytettävä tietorakenne, jolle on ominaista, että sen suurin (tai pienin) alkio on aina helposti saatavilla. Tärkeimpiä keon sovelluskohteita ovat mm. prioriteettijonon toteutus ja kekojärjestäminen.

Toteutus muokkaa

Keko on joko maksimikeko tai minimikeko riippuen siitä, onko tärkeää päästä nopeasti käsiksi tietojoukon suurimman vai pienimmän avaimen omaavaan alkioon. Yleensä keko hahmotetaan yhtenä tai useampana binääripuuna, joka toteuttaa (jotka toteuttavat) kekoehdon:

"Solmun avain on aina vähintään (tai enintään minimikeossa) yhtä suuri kuin sen lapsisolmujen avaimet."

Puun juurisolmulla on tällöin aina keon suurin (tai pienin) avain. Käytännössä keko tallennetaan kuitenkin usein taulukkona linkitetyn puurakenteen sijasta. Keon sisältöä muuttavat operaatiot on toteutettu siten, että ne säilyttävät kekoehdon totena. Toteutuksen yksityiskohdat riippuvat käytettävästä kekotyypistä. Yleisin kekotyyppi on binäärikeko. Muita variantteja ovat esimerkiksi fibonacci-keko ja binomikeko.

Operaatiot muokkaa

Yleisesti kekojen kanssa käytettyjä operaatioita ovat:

Suurimman (pienimmän) alkion etsiminen: find-max (find-min)
Suurimman (pienimmän) alkion poistaminen keosta: delete-max (delete-min)
Alkion avaimen arvon kasvattaminen ja pienentäminen: increase-key ja decrease-key
Uuden alkion lisääminen kekoon: insert
Kahden keon yhdistäminen yhdeksi isoksi keoksi: merge

Useimpien keko-operaatioiden nopeus on luokkaa O(log n). Joidenkin operaatioiden nopeus vaihtelee riippuen käytettävästä kekotyypistä. Vaikka nopeudet ovat samaa kertaluokkaa kuin yleensä hakupuilla, on keko toteutustavastaan johtuen käytännössä usein huomattavasti muita tietorakenteita nopeampi silloin, kun sen ominaisuuksia pystytään hyödyntämään.

Käyttökohteita muokkaa

Kekojärjestäminen on tehokas minimitilassa toimiva järjestämisalgoritmi, jonka pahimman tapauksen aikavaativuus on luokkaa O(n log n).
Prioriteettijono, eli jonorakenne, jossa korkeamman prioriteetin omaavat alkiot pääsevät "etuilemaan" niitä, joilla on alhaisempi prioriteetti, toteutetaan yleensä kekona.
Graafi- eli verkkoalgoritmit käyttävät usein kekoa esimerkiksi solmujen läpikäyntijärjestyksen tallentamiseen ja selvittämiseen.

Lähteet muokkaa

↑ Kivinen, Jyrki: Tietorakenteet-kurssin luentomateriaali (kevät 2008) (PDF) (sivu 284) Helsingin yliopiston tietojenkäsittelytieteen laitos. Arkistoitu 13.11.2021. Viitattu 13.11.2021.

Aiheesta muualla muokkaa

Kuvia tai muita tiedostoja aiheesta Keko (tietorakenne) Wikimedia Commonsissa

[1] Kivinen, Jyrki: Tietorakenteet-kurssin luentomateriaali (kevät 2008) (PDF) (sivu 284) Helsingin yliopiston tietojenkäsittelytieteen laitos. Arkistoitu 13.11.2021. Viitattu 13.11.2021.

[1]