# Prim’s – Minimum Spanning Tree (MST) |using Adjacency List and Min Heap

Earlier we have seen what is Prim’s algorithm is and how it works. In this article we will see its implementation using adjacency list and Min Heap.

We strongly recommend to read – prim’s algorithm and how it works and implementation of min-Heap

**Example**:

**Implementation – **Adjacency List and Min Heap

- Create min Heap of size = no of vertices.
- Create a heapNode for each vertex which will store two information. a). vertex b). key
- Use inHeap[] to keep track of the vertices which are currently in min heap.
- Create key[] to keep track of key value for each vertex. (keep updating it as heapNode key for each vertex)
- For each heapNode, Initialize key as MAX_VAL except the heapNode for the first vertex for which key will 0. (Start from first vertex).
- Insert all the heapNodes into min heap. inHeap[v] = true for all vertices.
- while minHeap is not empty
- Extract the min node from the heap, say it vertex
and add it to the MST.*u* - Decrease key: Iterate through all the adjacent vertices of above vertex
and if adjacent vertex (say it’s*u*) is still part of inHeap[] (means not in MST) and key of vertex*v*>*v*weight then key of vertex*u-v**v = u-v*

- Extract the min node from the heap, say it vertex
- We will use Result object to store the result of each vertex. Result object will store 2 information’s.
- First the parent vertex, means from which vertex you can visit this vertex. Example if for vertex
**v**, you have included edge**u-v**in mst[] then vertex**u**will be the parent vertex. - Second weight of edge u-v. If you add all these weights for all the vertices in mst[] then you will get Minimum spanning tree weight.

- First the parent vertex, means from which vertex you can visit this vertex. Example if for vertex

**Time Complexity:**

Total vertices: V, Total Edges : E

- O(logV) – to extract each vertex from queue. So for V vertices – O(VlogV)
- O(logV) – each time decrease the key value of a vertex. Decrease key will be called for at most once for each edge. So for total E edge – O(ElogV)
- So over all complexity: O(VlogV) + O(ElogV) = O((E+V)logV) =
**O(ElogV)**

See the animation below for more understanding

**Completed Code:**

**Output:**

Minimum Spanning Tree: Edge: 1 - 2 weight: 1 Edge: 2 - 0 weight: 3 Edge: 3 - 1 weight: 2 Edge: 4 - 3 weight: 2 Edge: 5 - 4 weight: 6 Total minimum key: 14

hi, in java we have priority queue for heaps data structure , but still you used traditional heap implementation. i tried to implement with priority queue, but i’m not able to modify heap data at particular node, as there nothing like getting n’th object in priority queue. here you used currentSize variable to modify the heap data. can you tell me this program can be implemented with priority queues or not?

Yes, it can be implemented using priority queue. Actually there are multiple ways this can be implemented, it can be done using priority queue with and without decrease key function. Please refer the links below:

1. with priority queue and decrease function (more time complexity) – https://algorithms.tutorialhorizon.com/prims-minimum-spanning-tree-mst-using-adjacency-list-and-priority-queue-with-decrease-key/

2. with priority queue and without decrease function (less time complexity) – https://algorithms.tutorialhorizon.com/prims-minimum-spanning-tree-mst-using-adjacency-list-and-priority-queue-without-decrease-key-in-oelogv/

3. Main article and all the methods – https://algorithms.tutorialhorizon.com/prims-algorithm-minimum-spanning-tree-mst/