Primerjava implementacij dvojiške in Fibonaccijeve kopice

GEORGIEV, ALEKSANDAR (author), 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.

• Language: Slovenian
• Keywords: primerjava podatkovnih struktur, vrste s prednostjo, dvojiška kopica, Fibonaccijeva kopica
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2022
• PID: 20.500.12556/RUL-140423
• COBISS.SI-ID: 123891459
• Publication date in RUL: 14.09.2022

Secondary language

• Language: English
• Title: Comparison of the implementations of binary and Fibonacci’s heap

Abstract

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.

• Keywords: data structure comparison, priority queue, binary heap, Fibonacci heap