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