Consider the heap of Figure 8.8(a) with one new record as in Figure 8.8(c). Notice that all paths are in order, except for the path from the new record at node 21 to the root. This prevents this tree from being a heap. To make it a heap, the insertion sort idea may be useful. Insert the new record at its proper place along the already sorted path from its predecessor node to the root, and allow 425 to work its way up along the path as far as it can go the reach its proper place. This can be done by comparing 425 to its predecessor and interchanging if it exceeds its predecessor's value. In this case, it does exceed that value, so interchange to obtain the tree shown in Figure 8.9(a).
All other paths remain sorted, as before. Now compare 425 at node 10 with its predecessor. Since it exceeds 123, interchange again to obtain Figure 8.9(b). Finally, compare 425 with its predecessor's value, and interchange to obtain Figure 8.9(c).
At this point, when 425 is compared to its predecessor's value, the 425 has reached its proper place. All paths must now be in order, since the path from node10 to the root is in order, and the interchanges have not disturbed the order along any other path.
This gives us the means to create a heap:
Start with records stored in the complete binary tree and process each node in turn, starting with node 2 and ending with node n.
The processing of the ith node is exactly the same processing as was done on the new record 425. Since nodes 1 to i - 1 will already have been processed prior to processing node i, the binary tree consisting of nodes 1 to i - 1 will already be a heap. Processing node i then, in effect, treats the record at node i as a new record and creates a new heap. For the example of twenty records, this procedure leads to the heap of Figure 8.8(a).