Keko (tietorakenne)

Keko (), joskus myös kasa, 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 
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
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 
 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 


 Aiheesta muualla 

Luokka:Ohjelmointi
Luokka:Tietorakenteet