Efikasne implementacije prioritetnog reda

master's thesis

• Title (english): Efficient implementation of the priority order
• Author: Mislav Žanić
• Mentor: Goranka Nogo (mentor)
• Committee member: Goranka Nogo (predsjednik povjerenstva)
• Committee member: Ivica Nakić (član povjerenstva)
• Committee member: Vanja Wagner (član povjerenstva)
• Committee member: Vedran Čačić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2022-07-20, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom smo radu prezentirali dvije asimptotski efikasne implementacije prioritetnog reda. U prvom smo poglavlju dali definiciju prioritetnog reda. Također, naveli smo i neke dodatne definicije koje smo koristili kroz ovaj rad. U drugom poglavlju bavili smo se analizom i opisom implementacije Fibonaccijeve hrpe. Dali smo intuitivan opis implementacije operacija prioritetnog reda i dokazali smo tvrdnje potrebne za analizu složenosti te opisali metodu kojom analiziramo složenost. Također smo dali pseudokodove kompleksnijih operacija. Na kraju smo poglavlja analizirali složenost metodom opisanom u istom poglavlju. U trećem smo poglavlju opisali i analizirali Brodalov red. Prvo smo opisali strogu strukturu Brodalovog reda. Potom smo dali opis pomoćne strukture podataka vodilje. Nakon toga opisali smo osnovne operacije nad stablima Brodalovog reda i implementaciju operacija prioirtetnog reda, kao i pseudokod. Na kraju smo napravili analizu složenosti operacija. U zadnjem smo poglavlju uspoređivali performanse Fibonaccijeve hrpe i Brodalovog reda pomoću sortiranja niza nasumice generiranih brojeva.

Abstract (english)

We have presented two asymptotically effcient implementation of a priority queue in this thesis. In the first chapter we have given the definition of priority queue. We have, also, given some additional definitions which we used throughout this thesis. In the second chapter we have analysed and described the implementation of Fibonacci heap. We gave a intuitive description of the implementation of priority queue operations and proved claims needed for the complexity analysis. We, also, briefly describe the complexity analysis method and gave pseudocodes of some operations. We ended the chapter by analysing complexity using the method described in this chapter. In the third chapter we have described and analysed Brodal queue. Firstly, we have described the strict structure of Brodal queue. Then we described a helper data structure called guide. After that, we have described simple tree operations link and delink and implementation of priority queue operations. Finally, we analysed the worst case complexity of implemented operations. In the last chapter, we have compared performance of Fibonacci heap and Brodal queue. We did this by sorting an array of randomly generated numbers using priority queues.

• Keywords: Fibonaccijeva hrpa; pseudokodovi kompleksnijih operacija; Brodalov red
• Keywords (english): Fibonacci heap; pseudocodes; Brodal's queue
• Language: croatian
• URN:NBN: urn:nbn:hr:217:715602
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2022-09-16 09:38:15