Primerjava implementacij dvojiške in Fibonaccijeve kopice

GEORGIEV, ALEKSANDAR (avtor), Dobravec, Tomaž (mentor)

Namen diplomske naloge je bila primerjava dveh implementacij vrste s prednostjo, dvojiške in Fibonaccijeve kopice. Najprej smo ugotovili, kaj so podatkovne strukture, kaj so njihove funkcije in kako ocenjujemo njihovo hitrost. V nadaljevanju smo implementirali obe podatkovni strukturi v programskem jeziku Java in opisali njuno implementacijo. Predstavili smo tudi teoretično primerjavo obeh implementacij. Primerjali smo ju po časovni zahtevnosti v najslabšem primeru ter predstavili amortizirano časovno analizo. Nato smo obe podatkovni strukturi primerjali še s pomočjo sistema ALGator. Ustvarili smo teste in za zaključek analizirali rezultate izvajanja.

• Jezik: Slovenski jezik
• Ključne besede: primerjava podatkovnih struktur, vrste s prednostjo, dvojiška kopica, Fibonaccijeva kopica
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2022
• PID: 20.500.12556/RUL-140423
• COBISS.SI-ID: 123891459
• Datum objave v RUL: 14.09.2022

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Comparison of the implementations of binary and Fibonacci’s heap

Izvleček

The purpose of the thesis is to compare two different implementations of priority queues: binary heap and Fibonacci's heap. Firstly we defined what data structures are, what are their functions and how do we evaluate them. In the next part we implemented both data structures in the programming language Java and explained how they were implemented. Then we made a theoretical comparison where we compared the O notation in worst case scenario and amortised O notation. After that we compared both data structures in the ALGator system. We made tests and at the end we determined which data structure is better in which use case.

• Ključne besede: data structure comparison, priority queue, binary heap, Fibonacci heap