Java Reference
In-Depth Information
/ ** BuildaHuffmantreefromlisthufflist * /
staticHuffTree<Character>buildTree(){
HuffTreetmp1,tmp2,tmp3=null;
while(Hheap.heapsize()>1){//Whiletwoitemsleft
tmp1=Hheap.removemin();
tmp2=Hheap.removemin();
tmp3=newHuffTree<Character>(tmp1.root(),tmp2.root(),
tmp1.weight()+tmp2.weight());
Hheap.insert(tmp3); //Returnnewtreetoheap
}
returntmp3; //Returnthetree
}
Figure5.29 Implementation for the Huffman tree construction function.
buildHuff takes as input fl , the min-heap of partial Huffman trees, which
initially are single leaf nodes as shown in Step 1 of Figure 5.25. The body of
function buildTree consists mainly of a for loop. On each iteration of the
for loop, the first two partial trees are taken off the heap and placed in variables
temp1 and temp2 . A tree is created ( temp3 ) such that the left and right subtrees
are temp1 and temp2 , respectively. Finally, temp3 is returned to fl .
V
U
X
L1
L2
Figure5.30 An impossible Huffman tree, showing the situation where the two
nodes with least weight, l 1 and l 2 , are not the deepest nodes in the tree. Triangles
represent subtrees.
Proof: The proof is by induction on n, the number of letters.
• Base Case: For n = 2, the Huffman tree must have the minimum external
path weight because there are only two possible trees, each with identical
weighted path lengths for the two leaves.
• Induction Hypothesis: Assume that any tree created by buildHuff that
contains n 1 leaves has minimum external path length.
• Induction Step: Given a Huffman tree T built by buildHuff with n
leaves, n 2, suppose that w 1 w 2 w n where w 1 to w n are
the weights of the letters. Call V the parent of the letters with frequencies w 1
and w 2 . From the lemma, we know that the leaf nodes containing the letters
with frequencies w 1 and w 2 are as deep as any nodes in T. If any other leaf
Search WWH ::




Custom Search