CHAP. 10] BINARY TREES 245
Accordingly, in a heap, the value ofNexceeds the value of every one of its descendants. In particular, the
root ofHis a largest value ofH.
Aminheapis defined analogously: The value ofNis less than or equal to the value at each of its children.
EXAMPLE 10.8 Consider the complete binary treeHin Fig.10-11(a). Observe thatHis a heap. This means,
in particular, that the largest element ofHappears at the “top” of the heap. Fig. 10-11(b) shows the sequential
representation ofHby the array TREE and the variable END. Accordingly:
(a) TREE[1] is the rootRofH.(b) TREE[2K] and TREE[2K+1] are the left and right children of TREE[K].
(c) The variable END=20 points to the last element inH.(d) The parent of any nonroot node TREE(J) is the node TREE[J÷2] (whereJ÷2 means integer division).
Observe that the nodes ofHon the same level appear one after another in the array TREE. The choice of 30
locations for TREE is arbitrary.
Fig. 10-11Inserting into a Heap
Figure 10-12 gives an algorithm which inserts a given data ITEM into a heapH.Remark:One must verify that Algorithm 10.3 does always yield a heap as a final tree. This is not difficult to see,
and we leave this verification to the reader.
EXAMPLE 10.9 Consider the heapHin Fig. 10-11. Suppose we want to insert ITEM=70 intoH. Simulating
Algorithm 10.3, we first adjoin ITEM as the last element of the complete tree; that is, as the right child of 48.