比较器和优先级队列
|
我正在编码霍夫曼代码，在此过程中，我导入文件，为每个字符生成霍夫曼代码，然后将二进制文件输出到文件中。为了导入字符，我正在使用读取每个字符的扫描器，将其放入具有读取字符值和频率为1的节点中。然后，将该节点添加到PriorityQueue中。由于Node类具有compareTo方法，该方法仅比较频率，因此如何在此特定的PriorityQueue中实现比较器，以便在队列中排序时比较字符？先谢谢了。
文字示例：
字符队列应按以下顺序排序：
[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]
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+\"]\";
}
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;
}
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();
}
没有找到相关结果
已邀请:
1 个回复
版萍层分
）来计数每个字母的频率，然后将每个字母的一个节点插入优先级队列。因此，在构造霍夫曼树本身时，您将从已显示为“最终”状态的优先级队列开始。然后，霍夫曼算法从优先级队列中反复提取两个节点，为这两个节点构造一个新的父节点，然后将新节点插入优先级队列中。