248 BINARY TREES [CHAP. 10
Thus Fig. 10-15(d) is the required heapHwithout its original rootR=95. Observe that we ringed the paths as
L=22 made its way down the tree.
Complexity of the Heap Algorithms
LetHbeaheapwithnnodes.SinceHisacompletetree,d≈log 2 nwheredisthedepthofH.Algorithm 10.3
tells us to let the new ITEM proceed up the tree, from level to level, until finding its appropriate place inH.
Algorithm 10.4 tells us to let the original last nodeLproceed down the tree, level by level, until finding its
appropriate place inH. In either case, the number of moves cannot exceed the depthdofH. Thus the running
timef (n)of either algorithm is very fast; specifically,f (n)= 0 (log 2 n). Accordingly, the heap is a much more
efficient way to implement a priority queueSthan either the linear array or sorted linear array mentioned at the
beginning of the section.
10.8Path Lengths, Huffman’s Algorithm
LetTbe an extended binary tree or 2-tree (Section 10.3). Recall that ifThasnexternal nodes, thenThas
n−1 internal nodes. Figure 10-3(b) shows a 2-tree with seven external nodes and hence 7− 1 =6 internal nodes.
Weighted Path Lengths
SupposeTis a 2-tree withnexternal nodes, and suppose each external node is assigned a (nonnegative)
weight. The weighted path length (or simply path length)Pof the treeTis defined to be the sum
P=W 1 L 1 +W 2 L 2 +···+WnLnwhereW 1 is the weight at an external nodeNi, andLiis the length of the path from the rootRto the nodeLi.
(The path lengthPexists even for nonweighted 2-trees where one simply assumes the weight 1 at each external
node.)
EXAMPLE 10.11 Figure 10-16 shows three 2-trees,T 1 ,T 2 ,T 3 , each having external nodes with the same
weights 2, 3, 5, and 11. The weighted path lengths of the three trees are as follows:
P 1 = 2 ( 2 )+ 3 ( 2 )+ 5 ( 2 )+ 11 ( 2 )= 42
P 2 = 2 ( 1 )+ 3 ( 3 )+ 5 ( 3 )+ 11 ( 2 )= 48
P 3 = 2 ( 3 )+ 3 ( 3 )+ 5 ( 2 )+ 11 ( 1 )= 36The quantitiesP 1 andP 3 indicate that the complete tree need not give a minimum path, and that the quantities
P 2 andP 3 indicate that similar trees need not give the same path length.
Fig. 10-16