Keko (tietorakenne)

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

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
  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.

    Aiheesta muualla
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.