Original title: Fibonacciho haldy - jejich varianty a alternativní datové struktury
Translated title: Fibonacci heaps - their variations and alternative data structures
Authors: Melka, Jakub ; Koubková, Alena (advisor) ; Koubek, Václav (referee)
Document type: Master’s theses
Year: 2012
Language: cze
Abstract: [cze] [eng]
V této práci budeme zkoumat Fibonacciho haldy a jejich varianty. Alternativní verze Fibonacciho hald, tzv. thin a thick haldu zavedli H. Kaplan a R. E. Tarjan v roce 2008. Srovnáme tyto haldy jak z experimentálního, tak z teoretického hlediska a do tohoto srovnání zahrneme i některé klasické druhy hald, jmenovitě párovací a regulární haldu. Při experimentech nás bude nejvíce zajímat celkový čas nutný pro běh algoritmu, který pracuje s haldou. Na výsledcích ukážeme, že thin a thick haldy jsou obvykle rychlejší, než Fibonacciho halda a pomalejší, než regulární haldy. Na závěr shrneme poznatky získané experimenty. In this paper we explore Fibonacci heaps and their variants. The alternative versions of the Fibonacci heap, the thin and thick heaps, were introduced by H. Kaplan and R. E. Tarjan in 2008. We compare these heaps from both experimental and theoretical point of view and we also include some classic types of heaps, namely regular and pairing heap. In our experiments we will be most interested in the total time required to run an algorithm that works with heap. The results show that thin and thick heaps are usually faster than the Fibonacci heap and slower than the regular heap. In conclusion, we summarize the knowledge gained from experiments.
Keywords: Fibonacci heap; heap; thick heap; thin heap; Fibonacciho halda; halda; thick halda; thin halda

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/44740

Permalink: http://www.nusl.cz/ntk/nusl-309032


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses