Utilities - Data Structures and Problem Solving Using Java - page 489

1 /**
2 * Construct the Huffman coding tree.
3 */
4 private void createTree( )
5 {
6 PriorityQueue<HuffNode> pq = new PriorityQueue<HuffNode>( );
7
8 for( int i = 0; i < BitUtils.DIFF_BYTES; i++ )
9 if( theCounts.getCount( i ) > 0 )
10 {
11 HuffNode newNode = new HuffNode( i,
12 theCounts.getCount( i ), null, null, null );
13 theNodes[ i ] = newNode;
14 pq.add( newNode );
15 }
16
17 theNodes[ END ] = new HuffNode( END, 1, null, null, null );
18 pq.add( theNodes[ END ] );
19
20 while( pq.size( ) > 1 )
21 {
22 HuffNode n1 = pq.remove( );
23 HuffNode n2 = pq.remove( );
24 HuffNode result = new HuffNode( INCOMPLETE_CODE,
25 n1.weight + n2.weight, n1, n2, null );
26 n1.parent = n2.parent = result;
27 pq.add( result );
28 }
29
30 root = pq.element( );
31 }
figure 12.22
A routine for constructing the Huffman coding tree
The tree produced by createTree is dependent on how the priority queue
breaks ties. Unfortunately, this means that if the program is compiled on two
different machines, with two different priority queue implementations, it is
possible to compress a file on the first machine, and then be unable to obtain
the original when attempting to uncompress on the second machine. Avoiding
this problem requires some additional work.