Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 10] BINARY TREES 247

Fig. 10-14

which is not a heap. (Note that both subtrees of 22 are still heaps.) Then we reheap, that is, we letL=22 sink
to its appropriate place as follows:

(a) The children ofL=22 are 85 and 70. The larger is 85. Since 22<85, interchange 22 and 85. This yields

the tree in Fig. 10-15(c).

(b) The children ofL=22 are now 33 and 55. The larger is 55. Since 22<55, interchange 22 and 55. This
yields the tree in Fig. 10-15(d).
(c) The children ofL=22 are now 15 and 11. The larger is 15. Since 22>15, the nodeL=22 has sunk to its
appropriate place in the heap.

Fig. 10-15