Skip to content

Commit 54b7c35

Browse files
gazeldxgazeldx
committed
1514-path-with-maximum-probability.md items are renamed to priority_queue.
1 parent 8ba76ee commit 54b7c35

File tree

2 files changed

+24
-22
lines changed

2 files changed

+24
-22
lines changed

‎en/1001-2000/1514-path-with-maximum-probability.md

+10-10
Original file line numberDiff line numberDiff line change
@@ -134,10 +134,10 @@ class Solution:
134134

135135
max_probabilities = [0 for node in range(n)]
136136
max_probabilities[start_node] = 1
137-
items = [(-1, start_node)]
137+
priority_queue = [(-1, start_node)]
138138

139-
while items:
140-
current_probability, current_node = heapq.heappop(items)
139+
while priority_queue:
140+
current_probability, current_node = heapq.heappop(priority_queue)
141141

142142
if current_node == end_node:
143143
return -current_probability
@@ -147,8 +147,8 @@ class Solution:
147147

148148
if probability_ > max_probabilities[target_node]:
149149
max_probabilities[target_node] = probability_
150-
# It may cause the same `target_node` added into `items` more than once, but it doesn't matter. Because only the one `heappush`ed first may change the `max_probabilities` data.
151-
heapq.heappush(items, (-probability_, target_node))
150+
# It may cause the same `target_node` added into `priority_queue` more than once, but it doesn't matter. Because only the one `heappush`ed first may change the `max_probabilities` data.
151+
heapq.heappush(priority_queue, (-probability_, target_node))
152152

153153
return 0
154154
```
@@ -167,11 +167,11 @@ class Solution:
167167

168168
max_probabilities = [0 for node in range(n)]
169169
max_probabilities[start_node] = 1
170-
items = [(-1, start_node)]
170+
priority_queue = [(-1, start_node)]
171171
visited = [False] * n # added 1
172172

173-
while items:
174-
current_probability, current_node = heapq.heappop(items)
173+
while priority_queue:
174+
current_probability, current_node = heapq.heappop(priority_queue)
175175

176176
if current_node == end_node:
177177
return -current_probability
@@ -189,8 +189,8 @@ class Solution:
189189

190190
if probability_ > max_probabilities[target_node]:
191191
max_probabilities[target_node] = probability_
192-
# It may cause the same `target_node` added into `items` more than once, but it doesn't matter. Because only the one `heappush`ed first may change the `max_probabilities` data.
193-
heapq.heappush(items, (-probability_, target_node))
192+
# It may cause the same `target_node` added into `priority_queue` more than once, but it doesn't matter. Because only the one `heappush`ed first may change the `max_probabilities` data.
193+
heapq.heappush(priority_queue, (-probability_, target_node))
194194

195195
return 0
196196
```

‎zh/1001-2000/1514-path-with-maximum-probability.md

+14-12
Original file line numberDiff line numberDiff line change
@@ -19,12 +19,14 @@ If there is no path from `start` to `end`, return 0. Your answer will be accepte
1919

2020
### [Example 2]
2121
![](../../images/examples/1514_2.png)
22+
2223
**Input**: `n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2`
2324

2425
**Output**: `0.30000`
2526

2627
### [Example 3]
2728
![](../../images/examples/1514_3.png)
29+
2830
**Input**: `n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2`
2931

3032
**Output**: `0.00000`
@@ -118,7 +120,7 @@ class Solution:
118120
```
119121

120122
### Dijkstra's algorithm using `heap sort`
121-
#### `heap sort` without using `visited`
123+
#### 1. `heap sort` without using `visited`
122124
```python
123125
import heapq
124126

@@ -132,10 +134,10 @@ class Solution:
132134

133135
max_probabilities = [0 for node in range(n)]
134136
max_probabilities[start_node] = 1
135-
items = [(-1, start_node)]
137+
priority_queue = [(-1, start_node)]
136138

137-
while items:
138-
current_probability, current_node = heapq.heappop(items)
139+
while priority_queue:
140+
current_probability, current_node = heapq.heappop(priority_queue)
139141

140142
if current_node == end_node:
141143
return -current_probability
@@ -145,13 +147,13 @@ class Solution:
145147

146148
if probability_ > max_probabilities[target_node]:
147149
max_probabilities[target_node] = probability_
148-
# It may cause the same `target_node` added into `items` more than once, but it doesn't matter. Because only the one `heappush`ed first may change the `max_probabilities` data.
149-
heapq.heappush(items, (-probability_, target_node))
150+
# It may cause the same `target_node` added into `priority_queue` more than once, but it doesn't matter. Because only the one `heappush`ed first may change the `max_probabilities` data.
151+
heapq.heappush(priority_queue, (-probability_, target_node))
150152

151153
return 0
152154
```
153155

154-
#### `heap sort` using `visited`
156+
#### 2. `heap sort` using `visited`
155157
```python
156158
import heapq
157159

@@ -165,11 +167,11 @@ class Solution:
165167

166168
max_probabilities = [0 for node in range(n)]
167169
max_probabilities[start_node] = 1
168-
items = [(-1, start_node)]
170+
priority_queue = [(-1, start_node)]
169171
visited = [False] * n # added 1
170172

171-
while items:
172-
current_probability, current_node = heapq.heappop(items)
173+
while priority_queue:
174+
current_probability, current_node = heapq.heappop(priority_queue)
173175

174176
if current_node == end_node:
175177
return -current_probability
@@ -187,8 +189,8 @@ class Solution:
187189

188190
if probability_ > max_probabilities[target_node]:
189191
max_probabilities[target_node] = probability_
190-
# It may cause the same `target_node` added into `items` more than once, but it doesn't matter. Because only the one `heappush`ed first may change the `max_probabilities` data.
191-
heapq.heappush(items, (-probability_, target_node))
192+
# It may cause the same `target_node` added into `priority_queue` more than once, but it doesn't matter. Because only the one `heappush`ed first may change the `max_probabilities` data.
193+
heapq.heappush(priority_queue, (-probability_, target_node))
192194

193195
return 0
194196
```

0 commit comments

Comments
 (0)