Keko (tietorakenne)
 |
Tähän artikkeliin tai osioon ei ole merkitty lähteitä, joten tiedot kannattaa tarkistaa muista tietolähteistä. Voit auttaa Wikipediaa lisäämällä artikkeliin tarkistettavissa olevia lähteitä ja merkitsemällä ne ohjeen mukaan. |
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 | muokkaa wikitekstiä]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 | muokkaa wikitekstiä]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 | muokkaa wikitekstiä]- 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 | muokkaa wikitekstiä]- ↑ 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 | muokkaa wikitekstiä]
Kuvia tai muita tiedostoja aiheesta Keko (tietorakenne) Wikimedia Commonsissa
