Practice Now
Prim's Algorithm
Fibonacci Heap
Graph Theory
Algorithm Implementation
Computer Science

How to implement Prim's algorithm with a Fibonacci heap?

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
AlgorithmsData Structures

Introduction

Prim's algorithm builds a minimum spanning tree by repeatedly choosing the cheapest edge that connects the growing tree to a new vertex. A Fibonacci heap improves the theoretical efficiency of the priority-queue part because decrease_key is amortized O(1), which is exactly the operation Prim performs frequently on dense graphs.

Why a Fibonacci Heap Helps

A standard heap-based Prim implementation already works well in practice, but a Fibonacci heap gives the classic asymptotic bound of O(E + V log V) because:

  • 'insert is amortized O(1)'
  • 'decrease_key is amortized O(1)'
  • 'extract_min is amortized O(log V)'

Prim uses decrease_key whenever it finds a cheaper connection to a vertex, so the data structure matters.

Minimal Runnable Python Implementation

The following example implements the core Fibonacci-heap operations needed for Prim's algorithm:

python
1from math import inf
2
3class Node:
4    def __init__(self, key, value):
5        self.key = key
6        self.value = value
7        self.degree = 0
8        self.mark = False
9        self.parent = None
10        self.child = None
11        self.left = self
12        self.right = self
13
14class FibHeap:
15    def __init__(self):
16        self.min_node = None
17        self.total_nodes = 0
18
19    def _iterate(self, start):
20        if start is None:
21            return
22        node = stop = start
23        flag = False
24        while True:
25            if node is stop and flag:
26                break
27            flag = True
28            yield node
29            node = node.right
30
31    def insert(self, key, value):
32        node = Node(key, value)
33        if self.min_node is None:
34            self.min_node = node
35        else:
36            node.left = self.min_node
37            node.right = self.min_node.right
38            self.min_node.right.left = node
39            self.min_node.right = node
40            if node.key < self.min_node.key:
41                self.min_node = node
42        self.total_nodes += 1
43        return node
44
45    def _link(self, y, x):
46        y.left.right = y.right
47        y.right.left = y.left
48        y.parent = x
49        if x.child is None:
50            x.child = y
51            y.left = y.right = y
52        else:
53            y.left = x.child
54            y.right = x.child.right
55            x.child.right.left = y
56            x.child.right = y
57        x.degree += 1
58        y.mark = False
59
60    def _consolidate(self):
61        degree_table = {}
62        roots = list(self._iterate(self.min_node))
63        for w in roots:
64            x = w
65            d = x.degree
66            while d in degree_table:
67                y = degree_table.pop(d)
68                if x.key > y.key:
69                    x, y = y, x
70                self._link(y, x)
71                d = x.degree
72            degree_table[d] = x
73        self.min_node = None
74        for node in degree_table.values():
75            node.left = node.right = node
76            if self.min_node is None:
77                self.min_node = node
78            else:
79                node.left = self.min_node
80                node.right = self.min_node.right
81                self.min_node.right.left = node
82                self.min_node.right = node
83                if node.key < self.min_node.key:
84                    self.min_node = node
85
86    def extract_min(self):
87        z = self.min_node
88        if z is not None:
89            if z.child is not None:
90                children = list(self._iterate(z.child))
91                for child in children:
92                    child.parent = None
93                    child.left.right = child.right
94                    child.right.left = child.left
95                    child.left = self.min_node
96                    child.right = self.min_node.right
97                    self.min_node.right.left = child
98                    self.min_node.right = child
99            z.left.right = z.right
100            z.right.left = z.left
101            if z is z.right:
102                self.min_node = None
103            else:
104                self.min_node = z.right
105                self._consolidate()
106            self.total_nodes -= 1
107        return z
108
109    def _cut(self, x, y):
110        if y.child is x:
111            y.child = x.right if x.right is not x else None
112        x.left.right = x.right
113        x.right.left = x.left
114        y.degree -= 1
115        x.parent = None
116        x.left = self.min_node
117        x.right = self.min_node.right
118        self.min_node.right.left = x
119        self.min_node.right = x
120        x.mark = False
121
122    def _cascading_cut(self, y):
123        z = y.parent
124        if z is not None:
125            if not y.mark:
126                y.mark = True
127            else:
128                self._cut(y, z)
129                self._cascading_cut(z)
130
131    def decrease_key(self, x, k):
132        if k > x.key:
133            raise ValueError("new key is greater than current key")
134        x.key = k
135        y = x.parent
136        if y is not None and x.key < y.key:
137            self._cut(x, y)
138            self._cascading_cut(y)
139        if x.key < self.min_node.key:
140            self.min_node = x
141
142def prim_with_fib_heap(graph, start):
143    heap = FibHeap()
144    handles = {}
145    parent = {v: None for v in graph}
146    in_tree = set()
147
148    for v in graph:
149        handles[v] = heap.insert(0 if v == start else inf, v)
150
151    mst = []
152    while heap.total_nodes:
153        node = heap.extract_min()
154        u = node.value
155        in_tree.add(u)
156        if parent[u] is not None:
157            mst.append((parent[u], u, node.key))
158        for v, weight in graph[u]:
159            if v not in in_tree and weight < handles[v].key:
160                parent[v] = u
161                heap.decrease_key(handles[v], weight)
162    return mst
163
164graph = {
165    "A": [("B", 1), ("C", 4)],
166    "B": [("A", 1), ("C", 2), ("D", 5)],
167    "C": [("A", 4), ("B", 2), ("D", 1)],
168    "D": [("B", 5), ("C", 1)],
169}
170
171print(prim_with_fib_heap(graph, "A"))

This code returns the edges of the minimum spanning tree together with the chosen edge weights.

How Prim Uses decrease_key

The important connection between the heap and the graph algorithm is this:

  • Each vertex sits in the heap with its current best known connection cost
  • When a cheaper edge to that vertex is found, Prim calls decrease_key
  • The next extract_min picks the cheapest frontier vertex

That is why Fibonacci heaps are a natural theoretical match for Prim's algorithm.

Common Pitfalls

The biggest mistake is implementing the graph logic correctly but not keeping heap handles for vertices. Without stable references to heap nodes, decrease_key becomes awkward or impossible.

Another issue is underestimating the complexity of Fibonacci-heap pointer operations. Bugs often appear in circular doubly linked lists, child promotion during extract_min, or cascading cuts after decrease_key.

Developers also sometimes choose Fibonacci heaps for every MST problem even though a binary heap is often simpler and faster in practice for ordinary input sizes. The Fibonacci heap wins mainly in theory and in carefully chosen workloads.

Finally, remember that Prim assumes a connected graph if you expect a single spanning tree. On a disconnected graph, the algorithm naturally yields a spanning forest instead.

Summary

  • Prim's algorithm repeatedly adds the cheapest edge connecting the tree to a new vertex.
  • Fibonacci heaps improve the theoretical complexity because decrease_key is amortized O(1).
  • A practical implementation needs insert, extract-min, decrease-key, cut, and cascading-cut.
  • Keep heap-node handles for vertices so Prim can update priorities efficiently.
  • Binary heaps are often simpler in practice, but Fibonacci heaps explain the classic asymptotic result.
Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms
Codemia
© 2026 Codemia
Resources
Legal
Social
All Rights Reserved.