Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Publication
Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
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.
Nikolaos Geroliminis, Patrick Stefan Adriaan Stokkink