The Self-Taught Computer Scientist

Chapter 15 Binary Heaps
169
First, you create a heap:
a_list = ['D', 'E', 'L', 'H', 'R', 'T']
heapify(a_list)
Then, you use a 
while
loop to pop all of its keys:
while len(a_list) > 0:
print(heappop(a_list)) 
The 
heapq
library also has a function called 
heappush
that inserts a key into a heap and rebalances it. 
Here is how to use 
heappush
to push an item onto your heap:
from heapq import heapify, heappush 
a_list = ['D', 'E', 'L', 'H', 'R', 'T']
heapify(a_list)
heappush(a_list, "Z")
print(a_list)
>> ['D', 'E', 'L', 'H', 'R', 'T', 'Z']
Python only provides a built- in function for min heaps, but you can easily create a max heap for 
numeric values by multiplying each value by −1. A max heap with strings as keys is more challenging 
to implement. Instead of using the 
heapq
library, you have to create one using a class or code a 
heap yourself.
Finally, you can use 
heapq
to handle priority- value pairs by storing tuples whose first element is 
the priority and the second element is the value, which could be anything. You will see an example 
of this in the next chapter when you code Dikijstras algorithm.
Connecting Ropes with Minimal Cost
You can use heaps to solve many problems that come up in your day- to- day programming as well as 
the ones that show up in technical interviews. For example, in a technical interview, you may be given 
a list of different rope lengths and asked to connect all of the ropes, two at a time, in the order that 
results in the lowest total cost. The cost of connecting two ropes is their sum, and the total cost is the 
sum of connecting all the ropes. So, for example, say you were given this list of ropes:
[5, 4, 2, 8] 
First, you could connect 8 and 2, then 4 and 10, and then 5 and 14. When you add up each cost, 
then, you get 43.

---