title: Huffman coding tree - Priority queue malfunctioning
body: <p>I'm trying to write a program for calculating Huffman codes for each character in a string.</p>
  
  <p>Here's my code::</p>
  
  <pre><code>import java.util.Collections;
  import java.util.PriorityQueue;
  
  public class HuffmanCode{
      PriorityQueue&lt;Node&gt; queue = new PriorityQueue&lt;Node&gt;();
      PriorityQueue&lt;Node&gt; queueCopy = new PriorityQueue&lt;Node&gt;();
  
      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 &lt; text.length(); i++) {
              letters[(int)(text.charAt(i))]++;
          }
          return letters;
      }
  
      public void fillQueue(int[] count) {
          for(int i = 0; i &lt; 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() &gt; 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 &amp;&amp; root.right == null)
              root.code = code + "";
      }
  
      public void displayCodes() {
          for(Node n: queue)
              System.out.println(n.character + " -&gt; " + n.weight + " -&gt; " + n.code);
      }
  }
  </code></pre>
  
  <p>Here's the <code>Node</code> class::</p>
  
  <pre><code>public class Node implements Comparable&lt;Node&gt;{
      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 &lt; e.weight)
              return -1;
          else if(this.weight == e.weight)
              return 0;
          else
              return 1;
      }
  }
  </code></pre>
  
  <p>If you debug the above code, you'll note that the elements in <code>queue</code> are not properly sorted. If <code>text</code> is 'Mississipi', for example, then <code>queue</code> contains M,i,p,s - which is wrong (because, <code>M</code> occurred once, <code>i</code> occured 4 times, <code>p</code> once and <code>s</code> occured 4 times). It should be M,p,s,i.</p>
  
  <p><strong>UPDATE</strong></p>
  
  <p>I replaced my <code>compareTo</code> method with:</p>
  
  <pre><code>@Override
  public int compareTo(Node e) {
  if(this.weight &lt; e.weight)
      return 1;
  else if(this.weight == e.weight)
      return 0;
  else
      return -1;
  }
  </code></pre>
  
  <p>Now, though the ordering is opposite to what's required, the sorting is correct. This time, when I entered <code>Mississipi</code>, the <code>queue</code> contained 'i,s,p,M'</p>