霍夫曼编码树 - 优先队列故障

我想写一个程序来计算字符串中每个字符的霍夫曼代码。霍夫曼编码树 - 优先队列故障

这里是我的代码::

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）' –

霍夫曼编码树 - 优先队列故障

回答

相关问题