Prim's MST with a Heap
Grow the tree from one vertex.
Prim's MST with a Heap is a free Coding Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
A Different Path to the MST
Prim's algorithm also finds a minimum spanning tree, but it grows one connected blob outward instead of sorting all the edges first. 🌱
Grow From One Vertex
Pick any starting vertex and mark it as visited. The tree begins as a single node and expands one edge at a time.
visited = [False] * nThe Frontier Idea
At each step you look at every edge crossing from the tree to the outside. Prim's always grabs the cheapest of those frontier edges.
A Heap Picks the Minimum
A min-heap makes finding the cheapest frontier edge fast. You push candidate edges in and pop the smallest weight out each round.
import heapq
heap = [(0, start)]Pop the Cheapest Edge
Pop the smallest entry from the heap. It gives you the weight and the next vertex that is cheapest to attach to the growing tree.
w, u = heapq.heappop(heap)Skip Stale Entries
A vertex may sit in the heap more than once. If you pop one that is already visited, just ignore it and pop again.
if visited[u]:
continueAdd and Expand
Mark the popped vertex visited and add its weight to the total. Then push each of its outgoing edges onto the heap for future steps.
visited[u] = True
total += w
for wt, v in adj[u]:
heapq.heappush(heap, (wt, v))Repeat Until Full
Keep popping and expanding until every vertex is visited. At that point the accumulated total is the minimum spanning tree weight.
The Running Time
Each edge can be pushed once and popped once, so heap-based Prim's runs in O(E log V), comparable to Kruskal's.
Prim's vs Kruskal's
Use Prim's on dense graphs with an adjacency list, and Kruskal's when you already have a plain edge list. Both yield the same MST weight.
It Looks Like Dijkstra
The heap loop mirrors Dijkstra's, but you compare raw edge weights, not path distances. Recognizing that pattern saves you coding time. ⚡
Quick Check
Recall how Prim's chooses its next edge each round.
Recap
You grew an MST with Prim's: start anywhere, use a min-heap to add the cheapest frontier edge, and skip stale visits. Great job! 🎉
Frequently asked questions
Is the “Prim's MST with a Heap” lesson free?
Yes — the full text of “Prim's MST with a Heap” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Prim's MST with a Heap”?
Grow the tree from one vertex. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Prim's MST with a Heap” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- DSU with Path Compression
- Union by Rank and Components
- Kruskal's Minimum Spanning Tree
- Prim's MST with a Heap