比較和優先級隊列

我正在編碼霍夫曼代碼的過程中，我導入一個文件，爲每個字符生成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

比較和優先級隊列

回答

相關問題