I am trying to do a MST algorithm implementation (Finding minimum spanning tree by extracting minimum edges and including every vertex) using Fibonacci Heaps. I want to minimize the time complexity by augmenting data structure if needed.

Approximate Algorithm :

`MST(G) 2 T ← {} // set that will store the edges of the MST 3 for i ← 1..n 4 Vi ← {i} 5 Ei ← {(i, j) : j is a vertex and (i, j) is an edge of G} // set of all edges incident with vertex i 6 end for 7 while there is more than one set Vi 8 choose any Vi 9 extract minimum weight edge (u, v) from Ei 10 one of the endpoints u of this edge is in Vi. let Vj be the set that contains the other endpoint v 11 if i != j then 12 T ← T ∪ {(u, v)} 13 combine Vi and Vj into Vi (destroying Vj ) 14 combine Ei and Ej into Ei (destroying Ej ) 15 end if 16 end while 17 return T 18 end MST `

Time complexity Analysis Approach:

The for loop of line 3 − 5 requires O(V) MAKE-HEAP operations and a total of O(E) INSERT operations in line 5. Note that the size of each Ei set can be at most O(V) by definition. The total time is thus O(V + E) ~ O(E) (Because Fibonacci Heaps can support constant insertions for both MakeHeap and Insertions.

Now for Line 7-15 – We can at most extract O(E) edges in line 9 taking a total of (E lg V) time if after every insert we also consolidate. (Debatable) Can we use consolidate a bit more efficiently?

Also, I feel that we are doing a couple of Union operations further. How to optimize it in a way that I try to save maximum time by using some auxiliary data structures if possible.