I'm in the process of coding Huffman Code where I import a file, generate huffman code for each character, then output the binary to a file. To import the characters I am using a scanner that reads each character, puts it in a node that has values of the read character and a frequency of 1. Then, the node is added to a PriorityQueue. Since the Node class has a compareTo method that compares only frequency, how can I implement a comparator to this specific PriorityQueue that compares the characters when sorting in queue?
Literal example: The queue of characters should be sorted as follows:
[A:1][A:1][A:1][B:1][C:1]
Next step:
[A:1][A:2][B:1][C:1]
Final:
[A:3][B:1][C:1]
Here are some snippets:
protected class Node implements Comparable<Node>{
Character symbol;
int frequency;
Node left = null;
Node right = null;
@Override
public int compareTo(Node n) {
return n.frequency < this.frequency ? 1 : (n.frequency == this.frequency ? 0 : -1);
}
public Node(Character c, int f){
this.symbol = c;
this.frequency = f;
}
public String toString(){
return "["+this.symbol +","+this.frequency+"]";
}
This is the PriorityQueue that needs a custom comparator:
public static PriorityQueue<Node> gatherFrequency(String file) throws Exception{
File f = new File(file);
Scanner reader = new Scanner(f);
PriorityQueue<Node> PQ = new PriorityQueue<Node>();
while(reader.hasNext()){
for(int i = 0; i < reader.next().length();i++){
PQ.add(new Node(reader.next().charAt(0),1));
}
}
if(PQ.size()>1){ //during this loop the nodes should be compared by character value
while(PQ.size() > 1){
Node a = PQ.remove();
Node b = PQ.remove();
if(a.symbol.compareTo(b.symbol)==0){
Node c = new Node(a.symbol, a.frequency + b.frequency);
PQ.add(c);
}
else break;
}
return PQ;
}
return PQ;
}
This is the new method I created using a HashMap:
public static Collection<Entry<Character,Integer>> gatherFrequency(String file) throws Exception{
File f = new File(file);
Scanner reader = new Scanner(f);
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
while(reader.hasNext()){
for(int i = 0; i < reader.next().length();i++){
Character key = reader.next().charAt(i);
if(map.containsKey(reader.next().charAt(i))){
int freq = map.get(key);
map.put(key, freq+1);
}
else{
map.put(key, 1);
}
}
}
return map.entrySet();
}
The standard approach to implementing Huffman trees is to use a hashmap (in Java, you'd probably use a HashMap<Character, Integer>
) to count the frequency for each letter, and insert into the priority queue one node for each letter. So when constructing the Huffman tree itself, you start out with a priority queue that is already in the "final" state that you showed. The Huffman algorithm then repeatedly extracts two nodes from the priority queue, constructs a new parent node for those two nodes, and inserts the new node into the priority queue.