Skip to content

Instantly share code, notes, and snippets.

@whyrusleeping
Created December 4, 2012 05:52
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save whyrusleeping/4201095 to your computer and use it in GitHub Desktop.
Save whyrusleeping/4201095 to your computer and use it in GitHub Desktop.
Huffman tree in java, kinda
import java.io.InputStream;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
public class HuffmanTree {
private Map<Character, Integer> counts;
public HuffmanTree (Map<Character, Integer> counts){
this.counts = counts;
}
public static HuffmanTree buildTree(int frequency){
PriorityQueue<HuffmanNode> pq = new PriorityQueue<HuffmanNode>();
/* Start terrible code that probably wont work */
Map<Character, Integer> huffmap = HuffmanNode.getCounts(file);
PriorityQueue<HuffmanNode> pq = new PriorityQueue<HuffmanNode>();
for(Map.Entry<Character, Integer> entry : huffmap.entrySet())
{
HuffmanNode n = new HuffmanNode();
n.frequency = entry.GetValue();
n.character = entry.GetKey();
pq.add(n)
}
//I really dont know java that well, so this is basically pseudocode
while(pq.size() > 1)
{
HuffmanNode l = pq.remove();
HuffmanNode r = pq.remove();
HuffmanNode top = new HuffmanNode();
top.frequency = l.frequency + r.frequency;
top.left = l;
top.right = r;
pq.add(top);
}
//At this point, there should be only one node in the queue, and it should have all the other nodes under it, this is a complete huffman tree
return null;
}
public StringBuilder compress(InputStream inputFile){
Scanner scan = new Scanner(inputFile);
StringBuilder input = new StringBuilder();
while(scan.hasNext()){
input.append(scan);
System.out.println(input);
}
return input;
}
public StringBuilder decompress(StringBuilder inputString){
return inputString;
}
public String printSideways(){
return null;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment