C++ Prim's Algorithm Implementation

In this assignment, you will be implementing the Prim's algorithm to find a minimum spanning tree and its total weight. It should also compute π value for each node and key value for each node (show π and key array content.). You will also need to implement a Heap data structure. The example input graph is the following: 9 Helium Fluorine/5 Calcium/6 Aluminum Dysprosium/21 Calcium Fluorine/2 Dysprosium/12 Helium/6 Iodine Barium/24 Europium/14 Dysprosium Calcium/12 Aluminum/21 Europium/28 Europium Dysprosium/28 Fluorine/29 Iodine/14 Fluorine Calcium/2 Helium/5 Europium/29 Gallium Barium/17 Barium Iodine/24 Gallium/17 where the first number is the number of nodes/vertices followed by a blank line, then each line after that is a vertex name followed by other vertices reachable with a cost; line 3 indicates from Helium there is an edge to Fluorine (weight 5), and to Calcium (weight 6). Note: all edges are directed and that edges may appear more than once: Aluminum to Dysprosium, Dysprosium to Aluminum. You might see a line with a vertex name without any other vertices following. That means that there is no edge coming from the vertex. Input will end with a blank line (after node and edge information, a user hits return) 1. Using the given input, store this information as an adjacency list or an adjacency matrix. You should store them in alphabetical order. 2. Define a priority queue using a heap. A heap will be an array and its size will be same as the number of nodes in the graph. You will also need to define functions, build-heap(), decrease-key(), and extract-min(). You can add additional functions if necessary, but points are allocated to define these three functions. 3. Create arrays π and key. 4. Using the same data set, calculate a minimum spanning tree using Prim's algorithm by creating MST-Prim function and print the minimum spanning tree as follows, and also display the total tree weight, the final π array content, and final key array content: The minimum spanning tree produced by the Prim's algorithm consists of the following edges: Aluminum -> Dysprosium with key 21 Dysprosium -> Calcium with key 12 Calcium -> Fluorine with key 2 Fluorine -> Helium with key 5 Dysprosium -> Europium with key 28 Europium -> Iodine with key 14 Iodine -> Barium with key 24 Barium -> Gallium with key 17 The total tree weight is 123 The array pi content: pi[Aluminum]= none pi[Barium]= Iodine pi[Calcium]= Dysprosium pi[Dysprosium]= Aluminum pi[Europium]= Dysprosium pi[Fluorine]= Calcium pi[Gallium]= Barium pi[Helium]= Fluorine pi[Iodine]= Europium The array key content: key[Aluminum]=0 key[Barium]=24 key[Calcium]=12 key[Dysprosium]=21 key[Europium]=28 key[Fluorine]=2 key[Gallium]=17 key[Helium]=5 key[Iodine]=14 Print all vertex pairs (edges) with their weight in the order that they were added to the tree, and the total tree weight.