Binääri- ja Fibonacci-keot prioriteettijonon toteutukseen

Myllyoja, Henri (2018)
 
Avaa tiedosto
Lataukset: 



Myllyoja, Henri
2018

Tietotekniikka
Tieto- ja sähkötekniikan tiedekunta - Faculty of Computing and Electrical Engineering
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2018-02-07
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tty-201712282497
Tiivistelmä
Tämän työn tavoite on tutkia binääri- ja Fibonacci-kekojen soveltuvuutta prioriteettijonon toteutukseen ja vertailla niitä käytännöllisellä ja teoreettisella tasolla. Prioriteettijono on yleisesti käytössä oleva tietorakenne, jota käytetään muun muassa erilaisissa graafialgoritmeissa.

Binäärikeko on yksinkertainen ja tehokas rakenne prioriteettijonon toteutukseen. Se on myös yleisin tapa toteuttaa prioriteettijono ohjelmistoissa. Monet ohjelmointikielet tarjoavat binäärikekoprioriteettijonon standardikirjastoissaan. Toinen työssä käsiteltävä kekorakenne, Fibonacci-keko, tarjoaa keko-operaatiot asymptoottisesti binäärikekoa tehokkaammin monimutkaisemman rakenteen kustannuksella.

Kummankin keon rakenne esitellään yksityiskohtaisesti. Lisäksi niiden tehokkuuksia vertaillaan Dijkstran ja Primin algoritmeissa. Fibonacci-keolla toteutettuna kumpikin näistä algoritmeista on asymptoottisesti tehokkaampi.

Fibonacci-keon tehokkuusetuja voi kuitenkin olla käytännössä vaikea saavuttaa keon monimutkaisen rakenteen johdosta. Siten sen merkitys korostuu teoreettisena pohjana tehokkaammille tietorakenteille.
Kokoelmat