Data Structures & AlgorithmsAdvanced Graph Algorithms

Prim's Algorithm

LevelIntermediate

Duration75 mins

TopicAdvanced Graph Algorithms

3 / 4

Priority Queue Implementation — The Engine of Efficient Prim's

From Quadratic to Logarithmic — The Priority Queue Revolution

In the previous page, we implemented a naive version of Prim's algorithm with O(V²) complexity. For a graph with 1 million vertices, this means approximately 10¹² operations—far too slow for modern applications like continental network design, power grid optimization, or social network analysis.

The breakthrough comes from a deceptively simple insight: instead of scanning all vertices to find the minimum key, we can use a priority queue (min-heap) to efficiently track and extract the minimum. This single change reduces complexity to O((V + E) log V), making Prim's practical for graphs with millions of vertices.

What You Will Learn

By the end of this page, you will understand how priority queues enable efficient minimum extraction, the exact mechanics of the optimized Prim's algorithm, implementation patterns for different priority queue types, and the tradeoffs between various approaches.

Priority Queue Fundamentals

Before diving into the optimized algorithm, let's ensure we have a solid understanding of priority queues—the data structure that makes efficient Prim's possible.

What Is a Priority Queue?

A priority queue is an abstract data structure that maintains a collection of elements, each with an associated priority (in our case, the key value representing edge weight). It supports three core operations:

Priority Queue Operations
Operation	Description	Binary Heap Time
Insert(element, priority)	Add an element with given priority	O(log n)
ExtractMin()	Remove and return element with minimum priority	O(log n)
DecreaseKey(element, newPriority)	Reduce the priority of an existing element	O(log n)

The Binary Heap:

The most common priority queue implementation is the binary min-heap—a complete binary tree where each parent has a smaller priority than its children. This structure guarantees:

The minimum element is always at the root
The tree height is O(log n), bounding operation times
Array-based storage for cache-friendly traversal

Heap Property Visualization:

Converting Mermaid diagram...

Array Representation

A binary heap can be stored in an array where for element at index i: parent is at ⌊(i-1)/2⌋, left child at 2i+1, and right child at 2i+2. This eliminates pointer overhead and improves cache performance.

DecreaseKey — The Critical Operation

For Prim's algorithm, the most nuanced priority queue operation is DecreaseKey. This operation is essential because as the tree grows, we may discover shorter edges to vertices still in the queue.

Why DecreaseKey Matters:

Consider vertex D which initially has key[D] = 6 (via edge B-D). Later, when vertex C is added, we discover edge C-D with weight 3—a shorter connection! We must:

Update key[D] from 6 to 3
Adjust D's position in the priority queue to reflect its new, lower priority

Without DecreaseKey, we can't efficiently update priorities for vertices already in the queue.

DecreaseKey Implementation Challenge

Standard library priority queues in many languages (like Python's heapq or Java's PriorityQueue) don't directly support DecreaseKey. This requires workarounds—lazy deletion being the most common.

Two Approaches to Handle DecreaseKey:

Approach 1: True DecreaseKey

•Implement custom heap with element position tracking
•Maintain a map from vertex ID to heap index
•When decreasing key, update value and 'bubble up'
•Pro: Optimal O((V + E) log V) complexity
•Con: More complex implementation

Approach 2: Lazy Deletion

•Use standard library priority queue
•Insert new (priority, vertex) pair on each update
•Ignore outdated entries when extracting (skip if inTree[v] is true)
•Pro: Simple, uses standard library
•Con: Extra heap entries, O((V + E) log E) typical

Lazy Deletion in Detail:

The lazy deletion approach is pragmatic and widely used:

When we need to update a vertex's key, insert a new entry (newKey, vertex) into the heap
The old entry (oldKey, vertex) remains in the heap but is now 'stale'
When extracting minimum, check if the vertex is already in the tree
If yes, this is a stale entry—discard it and extract again
If no, this is a valid entry—process it

This trades some extra memory and heap operations for implementation simplicity.

The Optimized Algorithm

Now let's present the complete priority queue-optimized Prim's algorithm. We'll show the lazy deletion version as it's most commonly implemented in practice.

Algorithm Overview:

Initialize: all vertices have key[v] = ∞, except start which has key[start] = 0
Insert (0, start) into priority queue
While queue is not empty:
- Extract (key, u) with minimum key
- If u already in tree, skip (stale entry)
- Add u to tree
- For each neighbor v of u:
  - If v not in tree and edge weight < key[v]:
    - Update key[v] and parent[v]
    - Insert (key[v], v) into queue
Return MST edges from parent array

prims_optimized.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import heapq
from typing import List, Tuple
 
def prims_mst(n: int, edges: List[Tuple[int, int, int]], start: int = 0) -> Tuple[List[Tuple[int, int, int]], int]:
    """
    Prim's algorithm using priority queue with lazy deletion.
    
    Args:
        n: Number of vertices (0 to n-1)
        edges: List of (u, v, weight) tuples representing undirected edges
        start: Starting vertex for MST construction
    
    Returns:
        Tuple of (MST edges as list of (u, v, weight), total MST weight)
    """
    # Build adjacency list
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # Initialize tracking arrays
    in_tree = [False] * n
    key = [float('inf')] * n
    parent = [-1] * n
    
    # Initialize start vertex
    key[start] = 0
    
    # Priority queue: (key_value, vertex)
    # Python's heapq is a min-heap
    pq = [(0, start)]
    
    total_weight = 0
    
    while pq:
        # Extract minimum
        current_key, u = heapq.heappop(pq)
        
        # Skip if already processed (lazy deletion)
        if in_tree[u]:
            continue
        
        # Add vertex to tree
        in_tree[u] = True
        total_weight += current_key
        
        # Process all neighbors
        for v, weight in graph[u]:
            if not in_tree[v] and weight < key[v]:
                # Found a shorter edge to v
                key[v] = weight
                parent[v] = u
                heapq.heappush(pq, (weight, v))
    
    # Construct MST edge list from parent array
    mst_edges = []
    for v in range(n):
        if parent[v] != -1:
            mst_edges.append((parent[v], v, key[v]))
    
    return mst_edges, total_weight
 
 
# Example usage
if __name__ == "__main__":
    # Graph: 6 vertices, edges with weights
    edges = [
        (0, 1, 1),  # A-B
        (0, 2, 4),  # A-C
        (1, 2, 2),  # B-C
        (1, 3, 6),  # B-D
        (2, 3, 3),  # C-D
        (2, 4, 5),  # C-E
        (3, 4, 7),  # D-E
        (3, 5, 8),  # D-F
        (4, 5, 9),  # E-F
    ]
    
    mst, weight = prims_mst(6, edges)
    print(f"MST Edges: {mst}")
    print(f"Total Weight: {weight}")
    # Output: MST Edges: [(0, 1, 1), (1, 2, 2), (2, 3, 3), (2, 4, 5), (3, 5, 8)]
    # Output: Total Weight: 19

Step-by-Step Trace with Priority Queue

Let's trace the priority queue version using our 6-vertex example graph. Watch how the heap evolves and how lazy deletion handles stale entries.

Initial State:

key = [0, ∞, ∞, ∞, ∞, ∞] (vertex A = 0 starts with key 0)
in_tree = [F, F, F, F, F, F]
pq = [(0, A)]

Extract: (0, A) — minimum in queue Check: in_tree[A] = false → valid entry Action: Add A to tree, in_tree[A] = true

Process A's neighbors:

B: weight 1 < ∞ → key[B] = 1, parent[B] = A, push (1, B)
C: weight 4 < ∞ → key[C] = 4, parent[C] = A, push (4, C)

Updated State:

key = [0, 1, 4, ∞, ∞, ∞]
in_tree = [T, F, F, F, F, F]
pq = [(1, B), (4, C)]
total_weight = 0

Lazy Deletion in Action

Notice how entries (4, C) and (6, D) became stale when we found shorter paths. Instead of removing them, we simply ignored them when extracted. This is the essence of lazy deletion—defer cleanup until extraction time.

TypeScript and Java Implementations

Let's provide complete implementations in TypeScript and Java to demonstrate language-specific patterns:

prims.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
interface Edge {
    to: number;
    weight: number;
}
 
interface HeapEntry {
    key: number;
    vertex: number;
}
 
class MinHeap {
    private heap: HeapEntry[] = [];
    
    push(entry: HeapEntry): void {
        this.heap.push(entry);
        this.bubbleUp(this.heap.length - 1);
    }
    
    pop(): HeapEntry | undefined {
        if (this.heap.length === 0) return undefined;
        const min = this.heap[0];
        const last = this.heap.pop()!;
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.bubbleDown(0);
        }
        return min;
    }
    
    isEmpty(): boolean {
        return this.heap.length === 0;
    }
    
    private bubbleUp(idx: number): void {
        while (idx > 0) {
            const parent = Math.floor((idx - 1) / 2);
            if (this.heap[parent].key <= this.heap[idx].key) break;
            [this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
            idx = parent;
        }
    }
    
    private bubbleDown(idx: number): void {
        while (true) {
            let smallest = idx;
            const left = 2 * idx + 1;
            const right = 2 * idx + 2;
            
            if (left < this.heap.length && this.heap[left].key < this.heap[smallest].key) {
                smallest = left;
            }
            if (right < this.heap.length && this.heap[right].key < this.heap[smallest].key) {
                smallest = right;
            }
            if (smallest === idx) break;
            
            [this.heap[smallest], this.heap[idx]] = [this.heap[idx], this.heap[smallest]];
            idx = smallest;
        }
    }
}
 
function primsMST(
    n: number, 
    edges: [number, number, number][], 
    start: number = 0
): { mstEdges: [number, number, number][]; totalWeight: number } {
    // Build adjacency list
    const graph: Edge[][] = Array.from({ length: n }, () => []);
    for (const [u, v, w] of edges) {
        graph[u].push({ to: v, weight: w });
        graph[v].push({ to: u, weight: w });
    }
    
    const inTree: boolean[] = new Array(n).fill(false);
    const key: number[] = new Array(n).fill(Infinity);
    const parent: number[] = new Array(n).fill(-1);
    
    const pq = new MinHeap();
    key[start] = 0;
    pq.push({ key: 0, vertex: start });
    
    let totalWeight = 0;
    
    while (!pq.isEmpty()) {
        const { key: currKey, vertex: u } = pq.pop()!;
        
        // Skip stale entries
        if (inTree[u]) continue;
        
        inTree[u] = true;
        totalWeight += currKey;
        
        for (const { to: v, weight } of graph[u]) {
            if (!inTree[v] && weight < key[v]) {
                key[v] = weight;
                parent[v] = u;
                pq.push({ key: weight, vertex: v });
            }
        }
    }
    
    // Build MST edge list
    const mstEdges: [number, number, number][] = [];
    for (let v = 0; v < n; v++) {
        if (parent[v] !== -1) {
            mstEdges.push([parent[v], v, key[v]]);
        }
    }
    
    return { mstEdges, totalWeight };
}

Priority Queue Variants and Performance

The choice of priority queue implementation affects practical performance. Let's examine the options:

Priority Queue Implementation Comparison
Data Structure	Insert	ExtractMin	DecreaseKey	Practical Notes
Binary Heap	O(log n)	O(log n)	O(log n)*	Simple, cache-friendly, most common choice
Fibonacci Heap	O(1) amort.	O(log n) amort.	O(1) amort.	Best theoretical bounds, but complex and slow in practice
Pairing Heap	O(1)	O(log n) amort.	O(log n) amort.	Simpler than Fibonacci, competitive performance
d-ary Heap	O(logd n)	O(d logd n)	O(logd n)*	Tunable branching factor, good for certain workloads
Array (unsorted)	O(1)	O(n)	O(n)	Prim's becomes O(V²) — the naive version

* With Position Tracking

True O(log n) DecreaseKey requires tracking element positions in the heap. Many implementations use lazy deletion instead, avoiding this complexity at the cost of potential duplicate heap entries.

Practical Recommendation:

For most applications, a standard binary heap with lazy deletion provides the best balance of:

Implementation simplicity
Good cache performance
Reliable O((V + E) log V) behavior for typical graphs

Fibonacci heaps achieve better theoretical bounds but are rarely faster in practice due to:

High constant factors
Complex pointer-based structure (poor cache locality)
Only significant advantage for extremely dense graphs where DecreaseKey operations dominate

When Fibonacci Heaps Might Help:

For graphs where E >> V (very dense graphs), the amortized O(1) DecreaseKey of Fibonacci heaps can matter. In theoretical algorithm analysis, Fibonacci heaps give Prim's a complexity of O(E + V log V), but the practical crossover point is rarely reached.

Common Implementation Pitfalls

Implementing Prim's correctly requires avoiding several common mistakes. Understanding these pitfalls helps you debug implementations and avoid hours of frustration:

Common Bugs and Fixes

•Forgetting to skip stale entries — Without the if (inTree[u]) continue check, you'll process vertices multiple times, causing incorrect weights and potential infinite loops with certain graph structures.
•Comparing wrong values — The condition must be weight < key[v], not weight < currentKey. We compare the edge weight to the best known connection, not to the currently extracted key.
•Not initializing key[start] = 0 — If the start vertex has key = ∞, it will never be extracted first (or at all in some implementations).
•Adding edges to vertices already in tree — When processing neighbors, always check !inTree[v] before updating key and pushing to queue. Otherwise, you create incorrect MST structures.
•Using max-heap instead of min-heap — Some languages default to max-heap. Ensure you're using a min-heap or negate weights accordingly.
•Integer overflow — When using Integer.MAX_VALUE or similar for infinity, adding to it can cause overflow. Handle this explicitly or use a smaller 'infinity' value.
•0-indexed vs 1-indexed confusion — Be consistent about whether vertices are numbered 0 to n-1 or 1 to n. Off-by-one errors are common.

Debugging Tip

Print the heap contents and key array at each step during development. Verify that extracted vertices have the expected key values and that stale entries are correctly identified and skipped.

Summary: Priority Queue Implementation

We've transformed the naive O(V²) Prim's into an efficient O((V + E) log V) algorithm using priority queues:

Key Takeaways

•Priority queues enable O(log n) minimum extraction — Instead of O(V) linear scan, we extract minimum in O(log V) time.
•DecreaseKey is handled via lazy deletion — Rather than true DecreaseKey, we insert new entries and skip stale ones during extraction.
•Complete implementations require careful attention — Stale entry detection, correct comparisons, and proper initialization are essential.
•Binary heaps are the practical choice — Despite Fibonacci heaps' better theoretical bounds, binary heaps perform well for real-world graphs.
•Language-specific patterns vary — Python's heapq, Java's PriorityQueue, and custom TypeScript implementations each have idiomatic approaches.
•Trace through small examples — Watching the heap evolve step-by-step builds intuition and helps debug implementations.

What's Next:

The next page analyzes Prim's time complexity rigorously, proving the O((V + E) log V) bound and exploring how graph density affects performance. We'll also compare with Kruskal's complexity to understand when each algorithm is preferable.

Page Complete

You now understand how priority queues transform Prim's algorithm from O(V²) to O((V + E) log V). The lazy deletion technique handles DecreaseKey elegantly, making efficient implementations straightforward with standard library data structures.

3 / 4

Loading learning content...

Data Structures & AlgorithmsAdvanced Graph Algorithms

Prim's Algorithm

LevelIntermediate

Duration75 mins

TopicAdvanced Graph Algorithms

3 / 4

Priority Queue Implementation — The Engine of Efficient Prim's

From Quadratic to Logarithmic — The Priority Queue Revolution

What You Will Learn

Priority Queue Fundamentals

Before diving into the optimized algorithm, let's ensure we have a solid understanding of priority queues—the data structure that makes efficient Prim's possible.

What Is a Priority Queue?

Priority Queue Operations
Operation	Description	Binary Heap Time
Insert(element, priority)	Add an element with given priority	O(log n)
ExtractMin()	Remove and return element with minimum priority	O(log n)
DecreaseKey(element, newPriority)	Reduce the priority of an existing element	O(log n)

The Binary Heap:

The most common priority queue implementation is the binary min-heap—a complete binary tree where each parent has a smaller priority than its children. This structure guarantees:

The minimum element is always at the root
The tree height is O(log n), bounding operation times
Array-based storage for cache-friendly traversal

Heap Property Visualization:

Converting Mermaid diagram...

Array Representation

DecreaseKey — The Critical Operation

Why DecreaseKey Matters:

Consider vertex D which initially has key[D] = 6 (via edge B-D). Later, when vertex C is added, we discover edge C-D with weight 3—a shorter connection! We must:

Update key[D] from 6 to 3
Adjust D's position in the priority queue to reflect its new, lower priority

Without DecreaseKey, we can't efficiently update priorities for vertices already in the queue.

DecreaseKey Implementation Challenge

Standard library priority queues in many languages (like Python's heapq or Java's PriorityQueue) don't directly support DecreaseKey. This requires workarounds—lazy deletion being the most common.

Two Approaches to Handle DecreaseKey:

Approach 1: True DecreaseKey

•Implement custom heap with element position tracking
•Maintain a map from vertex ID to heap index
•When decreasing key, update value and 'bubble up'
•Pro: Optimal O((V + E) log V) complexity
•Con: More complex implementation

Approach 2: Lazy Deletion

•Use standard library priority queue
•Insert new (priority, vertex) pair on each update
•Ignore outdated entries when extracting (skip if inTree[v] is true)
•Pro: Simple, uses standard library
•Con: Extra heap entries, O((V + E) log E) typical

Lazy Deletion in Detail:

The lazy deletion approach is pragmatic and widely used:

When we need to update a vertex's key, insert a new entry (newKey, vertex) into the heap
The old entry (oldKey, vertex) remains in the heap but is now 'stale'
When extracting minimum, check if the vertex is already in the tree
If yes, this is a stale entry—discard it and extract again
If no, this is a valid entry—process it

This trades some extra memory and heap operations for implementation simplicity.

The Optimized Algorithm

Now let's present the complete priority queue-optimized Prim's algorithm. We'll show the lazy deletion version as it's most commonly implemented in practice.

Algorithm Overview:

Initialize: all vertices have key[v] = ∞, except start which has key[start] = 0
Insert (0, start) into priority queue
While queue is not empty:
- Extract (key, u) with minimum key
- If u already in tree, skip (stale entry)
- Add u to tree
- For each neighbor v of u:
  - If v not in tree and edge weight < key[v]:
    - Update key[v] and parent[v]
    - Insert (key[v], v) into queue
Return MST edges from parent array

prims_optimized.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import heapq
from typing import List, Tuple
 
def prims_mst(n: int, edges: List[Tuple[int, int, int]], start: int = 0) -> Tuple[List[Tuple[int, int, int]], int]:
    """
    Prim's algorithm using priority queue with lazy deletion.
    
    Args:
        n: Number of vertices (0 to n-1)
        edges: List of (u, v, weight) tuples representing undirected edges
        start: Starting vertex for MST construction
    
    Returns:
        Tuple of (MST edges as list of (u, v, weight), total MST weight)
    """
    # Build adjacency list
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # Initialize tracking arrays
    in_tree = [False] * n
    key = [float('inf')] * n
    parent = [-1] * n
    
    # Initialize start vertex
    key[start] = 0
    
    # Priority queue: (key_value, vertex)
    # Python's heapq is a min-heap
    pq = [(0, start)]
    
    total_weight = 0
    
    while pq:
        # Extract minimum
        current_key, u = heapq.heappop(pq)
        
        # Skip if already processed (lazy deletion)
        if in_tree[u]:
            continue
        
        # Add vertex to tree
        in_tree[u] = True
        total_weight += current_key
        
        # Process all neighbors
        for v, weight in graph[u]:
            if not in_tree[v] and weight < key[v]:
                # Found a shorter edge to v
                key[v] = weight
                parent[v] = u
                heapq.heappush(pq, (weight, v))
    
    # Construct MST edge list from parent array
    mst_edges = []
    for v in range(n):
        if parent[v] != -1:
            mst_edges.append((parent[v], v, key[v]))
    
    return mst_edges, total_weight
 
 
# Example usage
if __name__ == "__main__":
    # Graph: 6 vertices, edges with weights
    edges = [
        (0, 1, 1),  # A-B
        (0, 2, 4),  # A-C
        (1, 2, 2),  # B-C
        (1, 3, 6),  # B-D
        (2, 3, 3),  # C-D
        (2, 4, 5),  # C-E
        (3, 4, 7),  # D-E
        (3, 5, 8),  # D-F
        (4, 5, 9),  # E-F
    ]
    
    mst, weight = prims_mst(6, edges)
    print(f"MST Edges: {mst}")
    print(f"Total Weight: {weight}")
    # Output: MST Edges: [(0, 1, 1), (1, 2, 2), (2, 3, 3), (2, 4, 5), (3, 5, 8)]
    # Output: Total Weight: 19

Step-by-Step Trace with Priority Queue

Let's trace the priority queue version using our 6-vertex example graph. Watch how the heap evolves and how lazy deletion handles stale entries.

Initial State:

key = [0, ∞, ∞, ∞, ∞, ∞] (vertex A = 0 starts with key 0)
in_tree = [F, F, F, F, F, F]
pq = [(0, A)]

Extract: (0, A) — minimum in queue Check: in_tree[A] = false → valid entry Action: Add A to tree, in_tree[A] = true

Process A's neighbors:

B: weight 1 < ∞ → key[B] = 1, parent[B] = A, push (1, B)
C: weight 4 < ∞ → key[C] = 4, parent[C] = A, push (4, C)

Updated State:

key = [0, 1, 4, ∞, ∞, ∞]
in_tree = [T, F, F, F, F, F]
pq = [(1, B), (4, C)]
total_weight = 0

Lazy Deletion in Action

TypeScript and Java Implementations

Let's provide complete implementations in TypeScript and Java to demonstrate language-specific patterns:

prims.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
interface Edge {
    to: number;
    weight: number;
}
 
interface HeapEntry {
    key: number;
    vertex: number;
}
 
class MinHeap {
    private heap: HeapEntry[] = [];
    
    push(entry: HeapEntry): void {
        this.heap.push(entry);
        this.bubbleUp(this.heap.length - 1);
    }
    
    pop(): HeapEntry | undefined {
        if (this.heap.length === 0) return undefined;
        const min = this.heap[0];
        const last = this.heap.pop()!;
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.bubbleDown(0);
        }
        return min;
    }
    
    isEmpty(): boolean {
        return this.heap.length === 0;
    }
    
    private bubbleUp(idx: number): void {
        while (idx > 0) {
            const parent = Math.floor((idx - 1) / 2);
            if (this.heap[parent].key <= this.heap[idx].key) break;
            [this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
            idx = parent;
        }
    }
    
    private bubbleDown(idx: number): void {
        while (true) {
            let smallest = idx;
            const left = 2 * idx + 1;
            const right = 2 * idx + 2;
            
            if (left < this.heap.length && this.heap[left].key < this.heap[smallest].key) {
                smallest = left;
            }
            if (right < this.heap.length && this.heap[right].key < this.heap[smallest].key) {
                smallest = right;
            }
            if (smallest === idx) break;
            
            [this.heap[smallest], this.heap[idx]] = [this.heap[idx], this.heap[smallest]];
            idx = smallest;
        }
    }
}
 
function primsMST(
    n: number, 
    edges: [number, number, number][], 
    start: number = 0
): { mstEdges: [number, number, number][]; totalWeight: number } {
    // Build adjacency list
    const graph: Edge[][] = Array.from({ length: n }, () => []);
    for (const [u, v, w] of edges) {
        graph[u].push({ to: v, weight: w });
        graph[v].push({ to: u, weight: w });
    }
    
    const inTree: boolean[] = new Array(n).fill(false);
    const key: number[] = new Array(n).fill(Infinity);
    const parent: number[] = new Array(n).fill(-1);
    
    const pq = new MinHeap();
    key[start] = 0;
    pq.push({ key: 0, vertex: start });
    
    let totalWeight = 0;
    
    while (!pq.isEmpty()) {
        const { key: currKey, vertex: u } = pq.pop()!;
        
        // Skip stale entries
        if (inTree[u]) continue;
        
        inTree[u] = true;
        totalWeight += currKey;
        
        for (const { to: v, weight } of graph[u]) {
            if (!inTree[v] && weight < key[v]) {
                key[v] = weight;
                parent[v] = u;
                pq.push({ key: weight, vertex: v });
            }
        }
    }
    
    // Build MST edge list
    const mstEdges: [number, number, number][] = [];
    for (let v = 0; v < n; v++) {
        if (parent[v] !== -1) {
            mstEdges.push([parent[v], v, key[v]]);
        }
    }
    
    return { mstEdges, totalWeight };
}

Priority Queue Variants and Performance

The choice of priority queue implementation affects practical performance. Let's examine the options:

Priority Queue Implementation Comparison
Data Structure	Insert	ExtractMin	DecreaseKey	Practical Notes
Binary Heap	O(log n)	O(log n)	O(log n)*	Simple, cache-friendly, most common choice
Fibonacci Heap	O(1) amort.	O(log n) amort.	O(1) amort.	Best theoretical bounds, but complex and slow in practice
Pairing Heap	O(1)	O(log n) amort.	O(log n) amort.	Simpler than Fibonacci, competitive performance
d-ary Heap	O(logd n)	O(d logd n)	O(logd n)*	Tunable branching factor, good for certain workloads
Array (unsorted)	O(1)	O(n)	O(n)	Prim's becomes O(V²) — the naive version

* With Position Tracking

True O(log n) DecreaseKey requires tracking element positions in the heap. Many implementations use lazy deletion instead, avoiding this complexity at the cost of potential duplicate heap entries.

Practical Recommendation:

For most applications, a standard binary heap with lazy deletion provides the best balance of:

Implementation simplicity
Good cache performance
Reliable O((V + E) log V) behavior for typical graphs

Fibonacci heaps achieve better theoretical bounds but are rarely faster in practice due to:

High constant factors
Complex pointer-based structure (poor cache locality)
Only significant advantage for extremely dense graphs where DecreaseKey operations dominate

When Fibonacci Heaps Might Help:

Common Implementation Pitfalls

Implementing Prim's correctly requires avoiding several common mistakes. Understanding these pitfalls helps you debug implementations and avoid hours of frustration:

Common Bugs and Fixes

•Forgetting to skip stale entries — Without the if (inTree[u]) continue check, you'll process vertices multiple times, causing incorrect weights and potential infinite loops with certain graph structures.
•Comparing wrong values — The condition must be weight < key[v], not weight < currentKey. We compare the edge weight to the best known connection, not to the currently extracted key.
•Not initializing key[start] = 0 — If the start vertex has key = ∞, it will never be extracted first (or at all in some implementations).
•Adding edges to vertices already in tree — When processing neighbors, always check !inTree[v] before updating key and pushing to queue. Otherwise, you create incorrect MST structures.
•Using max-heap instead of min-heap — Some languages default to max-heap. Ensure you're using a min-heap or negate weights accordingly.
•Integer overflow — When using Integer.MAX_VALUE or similar for infinity, adding to it can cause overflow. Handle this explicitly or use a smaller 'infinity' value.
•0-indexed vs 1-indexed confusion — Be consistent about whether vertices are numbered 0 to n-1 or 1 to n. Off-by-one errors are common.

Debugging Tip

Print the heap contents and key array at each step during development. Verify that extracted vertices have the expected key values and that stale entries are correctly identified and skipped.

Summary: Priority Queue Implementation

We've transformed the naive O(V²) Prim's into an efficient O((V + E) log V) algorithm using priority queues:

Key Takeaways

•Priority queues enable O(log n) minimum extraction — Instead of O(V) linear scan, we extract minimum in O(log V) time.
•DecreaseKey is handled via lazy deletion — Rather than true DecreaseKey, we insert new entries and skip stale ones during extraction.
•Complete implementations require careful attention — Stale entry detection, correct comparisons, and proper initialization are essential.
•Binary heaps are the practical choice — Despite Fibonacci heaps' better theoretical bounds, binary heaps perform well for real-world graphs.
•Language-specific patterns vary — Python's heapq, Java's PriorityQueue, and custom TypeScript implementations each have idiomatic approaches.
•Trace through small examples — Watching the heap evolve step-by-step builds intuition and helps debug implementations.

What's Next:

Page Complete

3 / 4