Create the Huffman code requires the use of a priority queue. The method is as follows:

Find the frequency of each character in the String.

Create a priority queue and insert the character/frequency pairs.

While the priority queue has more than one element in it:

Take the two front element off the priority queue.

Make a "tree" from the characters (or trees).

Put the tree and combined frequency back into the priority queue.

The final element left in the priority queue is the "tree" used to generate the Huffman codes. (We'll skip generating the codes; just print out the "tree".). The Nodes ("H", 1) and ("!", 2) come out first ( in that order). We combine them to form the node ("(H,!)", 3). That goes into the PQ. Then ("(H,!)", 3) and ("A", 10) come out of the PQ. We combine them to form the Node ("((H,!),A)", 12), and it goes back into the PQ. At this point there is only one Node in the PQ, so it has the "tree" in it. The String "((H,!),A)" gets printed as the "tree".

import java.util.HashMap;

import java.util.PriorityQueue;

import java.util.Scanner;

public class HuffmanDT {

private static final Scanner KBD = new Scanner(System.in);

static int IdCounter = 0; // used to number each node with unique Id

static class Node implements Comparable {

public char letter; // the letter from the string, or '#' if inner node

public int Id; // unique Id (used to generate DOT graph)

public int freq; // counts number of occurrences

public Node left; // pointer to left child, if any

public Node right; // pointer to right child, if nay

Node( char l, int f, Node lft, Node rt ) {

Id = IdCounter++;

letter = l; freq = f; left = lft; right = rt;

}

/**

* returns whether node is a leaf.

* @return true if leaf, false otherwise.

*/

public boolean isLeaf() { return left==null && right==null; }

@Override

/**

* compareTo: needed because nodes will be kept in priority queue that

* keeps node with smallest freq value at the root.

*/

public int compareTo(Object o) {

return freq - ((Node) o).freq;

}

}

/**

* computes the frequency associated with each letter found in the string s.

* @param s the string containing the characters to encode.

* @return a hashMap of the characters and their associated frequencies (as ints)

*/

private static HashMap getLetterFrequencies( String s ) {

HashMap freq = new HashMap();

for ( int i=0; i< s.length(); i++ ) {

char c = s.charAt(i);

if ( freq.containsKey( c ) )

freq.put( c, freq.get( c )+1 );

else

freq.put( c, 1 );

}

return freq;

}

/** TO DO

* Create a priority queue and insert the character/frequency pairs.

* While the priority queue has more than one element in it

* Take the two front element off the priority queue.

* Make a "tree" from the characters (or trees).

* Put the tree and combined frequency back into the priority queue.

*/

/**

* MAIN ENTRY POINT

* @param args

*/

public static void main(String[] args) {

System.out.print("Enter the line of text below:");

String s = KBD.nextLine();

HashMap freqs = getLetterFrequencies( s );

System.out.println("Calculating Frequencies: "+ freqs);

}

}

Here is the output:

Enter a line of text below:

abccdddeeeeeffffffff

Calculating Frequencies:

(a, 1) (b, 1) (c, 2) (d, 3) (e, 5) (f, 8)

Processing the Priority Queue:

Combining (a, 1) and (b, 1)

Combining (c, 2) and ((a,b), 2)

Combining (d, 3) and ((c,(a,b)), 4)

Combining (e, 5) and ((d,(c,(a,b))), 7)

Combining (f, 8) and ((e,(d,(c,(a,b)))), 12)

Huffman 'tree': (f,(e,(d,(c,(a,b)))))