The Self-Taught Computer Scientist

Chapter 15 Binary Heaps
167
Computer scientists often store heaps in arrays. You can store a heap in a Python list by distributing 
the keys into a list based on their position in the tree (Figure 15.12).
Inside of your list, your heap’s root node is at index 0. Its left child is at index 1, and its right child 
node is at index 2. You can use a mathematical equation to find the position of a node’s child. For any 
node, 
k, its left child’s index is 2k + 1, and the right child’s index is 2k + 2. For example, the equation 
to find the right child of C is 2
 * 0 + 2, which equals 2. That means the right child for the node at 
index 0 is at index 2 (Figure 15.13).
When to Use Heaps
You can find the maximum or minimum value in a max or min heap in constant time, but removing 
the minimum node from a min heap or the maximum node from a max heap is logarithmic because 
after you remove the item, you have to balance the remaining nodes. Inserting data into a heap is 
logarithmic, and searching for data in a heap is O(
n).
Heaps are helpful anytime you have to execute tasks according to priority. For example, your 
operating system could use a heap to keep track of different tasks and allocate resources depending 
on each task’s priority. You can also use a heap to implement Dijkstra’s algorithm for finding the short-
est path between two nodes in a graph. Dijkstra’s algorithm, which you will learn about in Chapter 16, 
can help you solve routing problems, like determining how to get from one city to another and routing 
in computer networks. Computer scientists also use heaps in a sorting algorithm called 
heapsort.
Creating a Heap
Python has a library function called 
heapq
that makes it easy to create a min heap. Here is a program 
that uses the 
heapify
function from 
heapq
to heapify a list of seven elements:
from heapq import heapify
a_list = ['R', 'C', 'T', 'H', 'E', 'D', 'L']
heapify(a_list)
[0] [1] [2] [3] [4] [5] [6]