The Self-Taught Computer Scientist

Data Structures
164
A min heap’s parent node’s priority is always less than or equal to any child node’s priority, and 
the node with the lowest priority is the root of the tree. Figure 15.3 shows a min heap with the same 
integers as the max heap from Figure 15.2.
In a binary heap, the ordering (min or max) applies only to a parent node and its children. There is 
no sorting between sibling nodes. As you can see in Figure 15.3, the siblings are not in order (6 and 4).
Computer scientists call creating a heap from a data structure like an array heapifying. For example, 
let’s say you have an array of unsorted keys like this:
["R", "C", "T", "H", "E", "D", "L"]
To heapify this data, first, you add each piece of data as a node to a binary tree. You start at the top 
of your tree and then fill in child nodes left to right on each subsequent level, as shown in Figure 15.4.
Then, you balance your heap. Balancing a heap means reordering keys that are out of order. In this 
case, you start with the last parent node (T) and compare it with its leaf nodes. If any of the leaf nodes 
have a value smaller than that of the parent node, you swap it with the parent node (Figure 15.5).
10
8
6
3
2
1
4
Figure 15.2: A max heap has the highest priority node as the root.
1
2
3
6
4
8
10
Figure 15.3: A min heap has the lowest priority node as the root.
R
C
T
H
E
D
L
Figure 15.4: The result of heapifying an array

---

Chapter 15 Binary Heaps
165
In this case, D is the smallest of the three nodes (T, D, and L), so you swap it with its parent node T.
Next, you move to the next-last parent and its leaf nodes (C, H, and E). C comes before both H 
and E, so you don’t make any swaps on the left side of the tree (Figure 15.7).
Now, you move up a level and compare again (Figure 15.8).
C has the lowest value of the nodes R, C, and D, so you swap C with R. Now C is the tree’s root 
(Figure 15.9).