528
Graphs and Trees
f
k
m
p
c
a
s
The root value, s, belongs at the bottom right of the tree (the position of the last array element), and once
positioned there, s will never be looked at again. The previous value, m, has been temporarily displaced.
f
k
m
p
c
a
s
To insert m back into the heap, there is a series of “competitions” between the displaced element and
the child nodes of the empty node so that the largest value is promoted to fill the empty slot. Here m, k,
and p compete, and p is the winner.
f
k
m
p
c
a
s
Now m and f compete (remember that s is no longer considered), the largest value is m, and once m is
inserted, the heap has been reestablished.
f
k
m
p
c
a
s
a. Complete phase 2 of the process so that the array is sorted. (Hint: The next step is to throw the root
value, p, into the position currently occupied by f. The displaced value f must then be reinserted into
the tree.)
b. For phase 1, to construct the heap, put the original random elements into the binary tree. Consider the
leaf nodes to be temporarily in place, since their relative order does not matter. Beginning with the
rightmost node in the level above the leaves and working up level-by-level to the root, temporarily
displace that node element and then insert it using the “competition” rules described. Beginning with
the array r, w, f, g, k, y, d, construct a heap.