The Self-Taught Computer Scientist

Data Structures
170
[5, 4, 2, 8] # 8 + 2 = 10
[5, 4, 10] # 10 + 4 = 14
[5, 14] # 5 + 14 = 19
# 10 + 14 + 19 = 43
However, if you connect the ropes in a different order, you get a different answer. To get the correct 
answer, you need to connect the two smallest ropes each time, like this:
[5, 4, 2, 8] # 4 + 2 = 6
[5, 8, 6] # 6 + 5 = 11
[8, 11] # 8 + 11 = 19
# 6 + 11 + 19 = 36
The total cost when you approach the problem like this is 36, which is the correct answer.
You can use a min heap to write a function that solves this problem. Here is how to do it:
from heapq import heappush, heappop, heapify
def find_min_cost(ropes):
heapify(ropes)
cost = 0
while len(ropes) > 1:
sum = heappop(ropes) + heappop(ropes)
heappush(ropes, sum)
cost += sum
return cost
First you define a function 
find_min_cost
that takes your list of ropes as a parameter:
def find_min_cost(ropes):
Then, you use 
heapify
to turn 
ropes
into a min heap and define a variable called 
cost
to keep track 
of the total cost of adding all of the ropes.
heapify(ropes)
cost = 0
Next, you create a 
while
loop that runs as long as the length of 
ropes
is greater than 1.
while len(ropes) > 1:
Inside of your loop you use 
heappop
to get the two lowest values from your heap and add them up. 
Then you use 
heappush
to push their sum back onto your heap. Finally, you add their sum to cost.

---

Chapter 15 Binary Heaps
171
sum = heappop(ropes) + heappop(ropes)
heappush(ropes, sum)
cost += sum
When your loop ends, you return 
cost
, which contains the lowest cost for connecting all the ropes.
return cost
Vocabulary