/van-Emde-Boas-Tree

Implementation of Kruskal algorithm using vEB tree as well as other data structures and then compare them.

Primary LanguageC++

Problem Statement:

Study and implement Van Emde Boas Tree data structure with application to kruskal algorithm ( minimum spanning tree algorithm ) and comparison with other data structures which are Binary Heap and Fibonacci Heap.

Goal:

  • Comparative study to undestand dictionary operations implementation of van Emde Boas Tree such as insertion, search, delete, extract minimum.
  • Achieve minimum time complexity to implement kruskal algorithm by using suitable data structure.

Implementation:

  • Used binary heap, Fibonacci Heap and then vEB Tree to implement the algorithm which involved implementation of the dictionary opeartions- Insert, Delete, extract minimum.
  • Observed behaviour of all the three implementation with different type of inputs and plotted the observed changes into a graph.

Results:

Documented a report (report.pdf in documents section) of all the obversvations.