比较和优先级队列

我正在编码霍夫曼代码的过程中，我导入一个文件，为每个字符生成huffman代码，然后输出二进制文件。为了导入字符，我使用了一个读取每个字符的扫描器，将它放入具有读取字符值和频率为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+"]"; 
    }

这是需要定制比较时Queue：

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; 

}

这是我使用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(); 
    }

来源

2011-04-15 Trevor Arjeski

这似乎比它需要复杂得多。即使它们不是连续的，也不应该计数所有的'A'。 – 2011-04-15 15:28:13

他们将永远是连续的，如果他们在一个PriorityQueue按字符值排序 – 2011-04-15 15:31:04

标准的方法来实现哈夫曼树是使用的HashMap（在Java中，你可能会使用一个HashMap<Character, Integer>）来计算每个字母的频率，并插入到优先级队列中的一个节点每封信。因此，在构建霍夫曼树本身时，您将开始使用已显示为“最终”状态的优先级队列。霍夫曼算法然后从优先级队列中重复提取两个节点，为这两个节点构建新的父节点，并将新节点插入优先级队列。

来源

2011-04-15 15:36:55

比较和优先级队列

回答

相关问题