title: What is the time and space complexity of Huffman encoding?
body: <p>I´ve implemented a Huffman encoding algorithm by using (two) Hashmaps to store each unique character´s (stored as keys in the hashmaps) frequency and code (stored as value in the hashmaps). I am unsure of how I can determine the time and space complexity, can anyone help me find out and explain what these are?</p>
  
  <p>Some thoughts I have:
  Each unique character is stored once in each Hashmap, so is the space complexity O(2*n)=O(n)? </p>
  
  <p>I´ve read that time complexity is O(nlogn) (for some solutions) but do not understand <em>why</em> that is.</p>
  
  <hr>
  
  <p><em>First I build a frequency map from a string:</em></p>
  
  <pre><code>/**
   * builds a list of the occurring characters in a text and
   * counts the frequency of these characters
   */
  public void buildFrequencyMap(String string) {
      frequencyMap = new HashMap&lt;Character, Integer&gt;(); //key, value
      char[] stringArray = string.toCharArray();
  
      for(char c : stringArray) {
          if(frequencyMap.containsKey(c)) { //if the character has not been stored yet, store it
              frequencyMap.put(c, frequencyMap.get(c) + 1);
          } else {
              frequencyMap.put(c, 1);
          }
      }
  }
  </code></pre>
  
  <p><em>Then I build the tree:</em></p>
  
  <pre><code>/**
   * builds the huffman tree
   */
  public Node buildTree() {
      PriorityQueue&lt;Node&gt; queue = new PriorityQueue&lt;Node&gt;();
  
      //fill the queue with nodes constructed from a character and its frequency
      for(char i = 0; i &lt; 256; i++ ) { //256 - size of ASCII alphabet
          if(frequencyMap.containsKey(i) &amp;&amp; frequencyMap.get(i) &gt; 0) {
              queue.add(new Node(i, frequencyMap.get(i), null, null)); //create new leaf
          }
      }
  
      //if the indata only consists of 1 single character
      if(queue.size() == 1) {
          queue.add(new Node('\0', 1, null, null));
      }
      //otherwise
      //continuously merge nodes (two with the lowest frequency) to build the tree until only one node remains --&gt; becomes the root
      while(queue.size() &gt; 1) {
          Node left = queue.poll(); //first extracted child becomes the left child
          Node right = queue.poll(); //second extracted child becomes the right child
          Node parent = new Node('\0', (left.frequency + right.frequency), left, right);
          queue.add(parent);
      }
      return root = queue.poll(); //the remaining node in the queue becomes the root
  }
  </code></pre>
  
  <p><em>Lastly, the codemap is built:</em></p>
  
  <pre><code>/**
   * builds the codemap
   */
  public void buildCodeMap() {
      codeMap = new HashMap&lt;Character, String&gt;(); //key, value
      buildCode(root, "", codeMap);
  }
  
  public void buildCode(Node node, String code, HashMap&lt;Character, String&gt; codeMap) {
      if(!node.isLeaf()) { //if the current node is NOT a leaf
          buildCode(node.leftChild, code + '0', codeMap); //each time we go down at the LEFT side of the tree, encode a 0
          buildCode(node.rightChild, code + '1', codeMap); //each time we go down at the RIGHT side of the tree, encode a 1
      } else { //otherwise
          codeMap.put(node.character, code);
      }
  }
  </code></pre>