One way to implement the heap creation algorithm is to make use of a function, or routine, that works on a binary tree whose left and right subtrees are already heaps. The function does the "shifting" down of the root record until it becomes the root of a subtree that remains a heap, or until it reaches a terminal node. This "shift" routine need not do the interchanging along the way. Instead it can determine the final position of the root being shifted down, moving each record along that path to its predecessor, finally placing the root where it belongs.
Notice that the first heap creation algorithm requires testing the record being inserted along a path to the root against its current predecessor. Before this can be done, the program must test for whether or not there is a predecessor?/FONT>that is, whether the record has already reached the root. This test must precede every comparison. Similarly, in the second heap creation algorithm, the record being shifted down must be tested against its successors. Before doing this, it is necessary to test whether there are successors.
These tests can be avoided by always putting "plus infinity" at the root of the initial complete binary tree for the first algorithm, and "negative infinity" at the subtrees of all terminal nodes for the second algorithm. This is similar in effect to adding the search key to the end of the array in the linear search algorithm. Plus infinity and negative infinity stand for, respectively, any number larger or smaller than the numbers appearing in the binary tree. In this way, a record being inserted along a path in the first algorithm will never reach the root (so it will always have a predecessor with which it may be compared), and a record being shifted down in the second algorithm will always have successor nodes (since it will never become a terminal node).