Priority queue

Prim uses a priority queue efficiently.

Minimum key

In Prim each node has a keys value: the lowest cost to connect it to the tree. Each step picks the unvisited node with the smallest keys.

This selection can be done with linear search. The min_key(keys, visited) function does this selection.

Initial state

Initially keys is inf for all nodes; only the start node has keys[0] = 0. So the first pick is the start node.

The visited array starts as False for all nodes. The tree grows from a single node.

Exercise min_key function

Write min_key(keys, visited). Return the index of the unvisited node with the smallest keys. Print 0 with print(min_key([0, float('inf'), float('inf'), float('inf')], [False, False, False, False])).

Show example solution

def min_key(keys, visited):
    # Find the unvisited index with smallest keys
    best = float('inf')
    idx = -1
    for i in range(len(keys)):
        if not visited[i] and keys[i] < best:
            best = keys[i]
            idx = i
    return idx
print(min_key([0, float('inf'), float('inf'), float('inf')], [False, False, False, False]))

Test yourself

Min selection

if not visited[i] and keys[i] ____ best:

Show answer

if not visited[i] and keys[i] < best:

Which node does min_key return?
- The largest keys
- The smallest keys
- A random node
- The first unvisited
Show answer

The smallest keys — min_key returns the node with smallest keys.
Priority queue: match the terms

keys

Cost
visited

Visited
min_key

Selection
inf

Infinity

Next lesson: Visited set

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies