霍夫曼編碼樹 - 優先隊列故障

我想寫一個程序來計算字符串中每個字符的霍夫曼代碼。霍夫曼編碼樹 - 優先隊列故障

這裏是我的代碼::

import java.util.Collections; 
import java.util.PriorityQueue; 

public class HuffmanCode{ 
    PriorityQueue<Node> queue = new PriorityQueue<Node>(); 
    PriorityQueue<Node> queueCopy = new PriorityQueue<Node>(); 

    public void getCodes(String text) { 
     int[] count = countOccurences(text); 
     fillQueue(count); 
     makeHuffmanTree(); 
     assignCodes(); 
     displayCodes(); 
    } 

    public int[] countOccurences(String text) { 
     int[] letters = new int[256]; 
     for(int i = 0; i < text.length(); i++) { 
      letters[(int)(text.charAt(i))]++; 
     } 
     return letters; 
    } 

    public void fillQueue(int[] count) { 
     for(int i = 0; i < count.length; i++) { 
      if(count[i] != 0) { 
       queue.offer(new Node((char)i, count[i])); 
       queueCopy.offer(new Node((char)i, count[i])); 
      } 
     } 
    } 

    public void makeHuffmanTree() { 
     if(queue.size() > 1) { 
      Node node1 = queue.remove(); 
      Node node2 = queue.remove(); 
      queue.offer(new Node(node1, node2)); 
      makeHuffmanTree(); 
     } 
    } 

    public void assignCodes() { 
     assignCodes(queue.remove(), ""); 
    } 

    public void assignCodes(Node root, String code) { 
     if(root.left != null) 
      assignCodes(root.left, code + "0"); 
     if(root.right!= null) 
      assignCodes(root.right, code + "1"); 
     if(root.left == null && root.right == null) 
      root.code = code + ""; 
    } 

    public void displayCodes() { 
     for(Node n: queue) 
      System.out.println(n.character + " -> " + n.weight + " -> " + n.code); 
    } 
}

這裏的Node類::

public class Node implements Comparable<Node>{ 
    char character; 
    int weight; 
    Node left; 
    Node right; 
    String code = ""; 

    Node(char character, int weight) { 
     this.character = character; 
     this.weight = weight; 
    } 

    Node(Node node1, Node node2) { 
     weight = node1.weight + node2.weight; 
     left = node1; 
     right = node2; 
    } 

     }@Override 
    public int compareTo(Node e) { 
     if(this.weight < e.weight) 
      return -1; 
     else if(this.weight == e.weight) 
      return 0; 
     else 
      return 1; 
    } 
}

如果調試上面的代碼，你會注意到，在queue的元素是不能正確排序。例如，如果text是'Mississipi'，則queue包含M，i，p，s-這是錯誤的（因爲，M發生一次，i發生4次，p一次，並且s發生4次）。它應該是M，P，S，I。

UPDATE

我取代了我compareTo方法：現在

@Override 
public int compareTo(Node e) { 
if(this.weight < e.weight) 
    return 1; 
else if(this.weight == e.weight) 
    return 0; 
else 
    return -1; 
}

，雖然順序是相反的真實需要什麼，排序是正確的。此時，當我進入Mississipi，所述queue包含「I，S，P，M」

來源

2015-10-05 Saud

從的Javadoc PriorityQueue

這個隊列的頭是相對於指定的排序的最小元素。如果多個元素的價值最小，那麼頭是其中一個元素 - 領帶被任意破壞。隊列檢索操作輪詢，刪除，查看和元素訪問隊列頭部的元素。

而對於PriorityQueue.iterator（）

公共迭代迭代器（）返回在此隊列中的元素的迭代器。迭代器不會以任何特定順序返回元素。

如果你想要一個被排序的結構，你可以使用TreeSet。

來源

2015-10-05 14:48:42

我已更新我的問題。請看一下。 – Saud

@Saud「雖然排序與所需要的相反，」您正在返回與通常使用的符號相反的符號。認爲'sign（this.weight - e.weight）'或'Integer.compare（this.weight，e.weight）' –

霍夫曼編碼樹 - 優先隊列故障

回答

相關問題