Infoscience

Student project

Fibonacci Heaps

Binomial heaps are data structures implemented as a collection of binomial trees, (A binomial tree of order K can be constructed from two trees of order (K-1)). They can implement several methods: Min, Insert, Union, ExtractMin, DecreaseKey and Delete. Fibonacci heaps are similar to binomial heaps,howevere it figured that they had a better performance in what regards the amortized analysis, These methods have a cost of O(1) except for ExtractMin and Delete (O(lg n)) Fibonacci heaps are used to improve the cost of Dijikstra and Prim. We implemented first the algorithms of Binomial and Fibonacci. We then used ExtractMin of fibonacci so as to implement Prim and Dijikstra. We have made a bonus algorithm , Kruskal who is also a "Minimum Spanning Tree" algorithm.

    Reference

    • ALGO-STUDENT-2007-007

    Record created on 2007-03-05, modified on 2016-08-08

Related material