The Self-Taught Computer Scientist

R
C
T
H
E
D
L
Current Level
Figure 15.5: Swapping values to balance a heap
R
C
D
H
E
T
L
Figure 15.6: Swapping D and T is the first step to balance this heap.
R
C
D
H
E
T
L
Current Level
Figure 15.7: The left side of the heap was already balanced.

---

Data Structures
166
Now you “trickle down” the R node by comparing its value with its leaf nodes. If the R node has a 
value larger than one of its leaf nodes, you swap them and compare R node’s value with its new leaf 
nodes. You continue this as long as R either has a value larger than any of its leaf nodes or you reach 
the lowest level of the heap. E comes before R, so you swap them (Figure 15.10).
Now, your heap is balanced (Figure 15.11).
Current Level
rrent Level
R
C
D
H
E
T
L
Figure 15.8: Balancing the tree at the next level
Root Node
C
R
D
H
E
T
L
Figure 15.9: C is now the root node in your binary heap.
Current Level
C
R
D
H
E
T
L
Figure 15.10: The R node trickles down the tree as long as it has a larger value than any of its 
leaf nodes.
C
E
D
H
R
T
L
Figure 15.11: A balanced heap

---