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.