Priority queue
- Algorithms course
- Advanced
- Lesson 42/56
- 4 min
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.
Practice 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])).
Starter code
def min_key(keys, visited):
# Find the unvisited index with smallest keysSample 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]))Expected output
0
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Min selection
if not visited[i] and keys[i] ____ best:if not visited[i] and keys[i] < best:Explanation: < is right.
2 Which node does min_key return?
- The largest keys
- The smallest keys Correct answer
- A random node
- The first unvisited
Explanation: min_key returns the node with smallest keys.
3 Priority queue: match the terms
| Term | Meaning |
|---|---|
keys |
Cost |
visited |
Visited |
min_key |
Selection |
inf |
Infinity |