I’m trying to understand what to do with my homework problem. I am trying to create a Huffman Tree that will encode and decode messages in Java. I am given Strings and Frequency.
[a=10, b=15, c=12, e=3, nl=4, sp=13, t=1].
I know that with Huffman Tree you take the two lowest Frequencies and make them into a tree with the sum of their Frequency as the parent.
I understand that using a Priority Queue I can insert all the Frequency into it and use the remove()
method to take out the 2 lowest Frequency. Then add them together to get the Weight of them both, then insert that Weight back into the Queue and repeat.
The final Tree should hold weight of
[58=root, root.left = 33, root.right = 25]
[33.left = 18, 18.left = 8, 8.left = 4]
I am not sure exactly how to even begin to implement a Huffman Tree code that will be able to create the tree with the Frequency and display the Tree. I’ve look at other codes and it seem like they all are creating from Streaming Input Code or so.
Any help would be great in getting me going. Thanks in advance!
I’m suppose to print out with a format like : (pre-order traversal)
58
- 33
- - 18
- - - 8
- - - - 4
- - - - - 1:t
- - - - - 3:e
- - - - 4:nl
- - - 10:a
- - 15:b
- 25
- - 12:c
- - 13:sp
Steps to build Huffman TreeCreate a new internal node with a frequency equal to the sum of the two nodes frequencies. Make the first extracted node as its left child and the other extracted node as its right child. Add this node to the min heap. Repeat steps#2 and #3 until the heap contains only one node.
Are you asking if (valid) huffman trees for the same input can be different? If so, the answer is Yes.
Huffman Coding Complexity The time complexity for encoding each unique character based on its frequency is O(nlog n) . Extracting minimum frequency from the priority queue takes place 2*(n-1) times and its complexity is O(log n) . Thus the overall complexity is O(nlog n) .
The Huffman tree is the binary tree with minimum external path weight, i.e., the one with the minimum sum of weighted path lengths for the given set of leaves. So the goal is to build a tree with the minimum external path weight.
import java.util.PriorityQueue;
public class Node implements Comparable<Node> {
Node left;
Node right;
Node parent;
String text;
int frequency;
public Node(String textIn, int frequencyIn) {
text = textIn;
frequency = frequencyIn;
}
public Node(int frequencyIn) {
text = "";
frequency = frequencyIn;
}
public int compareTo(Node n) {
if (frequency < n.frequency) {
return -1;
}
else if(frequency > n.frequency) {
return 1;
}
return 0;
}
public static void printFromPreOrder(Node n, String dashes) {
// print with colon if leaf node
if (n.text != "") {
System.out.println(dashes + n.frequency + ":" + n.text);
}
else {
System.out.println(dashes + n.frequency);
}
// Start recursive on left child then right
if (n.left != null) {
printFromPreOrder(n.left, dashes + "-");
}
if (n.right != null) {
printFromPreOrder(n.right, dashes + "-");
}
}
// Returns root node to pass to printFromPreOrder
public static Node makeHuffmanTree(int frequencies[], String text[]) {
PriorityQueue<Node> queue = new PriorityQueue<Node>();
for (int i = 0; i < text.length; i++) {
Node n = new Node(text[i], frequencies[i]);
queue.add(n);
}
Node root = null;
while (queue.size() > 1) {
Node least1 = queue.poll();
Node least2 = queue.poll();
Node combined = new Node(least1.frequency + least2.frequency);
combined.right = least1;
combined.left = least2;
least1.parent = combined;
least2.parent = combined;
queue.add(combined);
// Keep track until we actually find the root
root = combined;
}
return root;
}
public static void main(String[] args) {
int frequencies[] = {10, 15, 12, 3, 4, 13, 1};
String text[] = {"a", "b", "c", "e", "nl", "sp", "t"};
Node root = Node.makeHuffmanTree(frequencies, text);
Node.printFromPreOrder(root, "");
}
}
This will work for you. I have included your example, but it should work for any number of frequencies and text. Just make sure the frequencies and text are of the same size because I did no error checking.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With