Question
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 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
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
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)))))
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started