title: Huffman tree implementation using minheap
body: <p>In the book I'm using for my class (and from what I've seen from a few other places), it seems like the algorithm for creating a huffman tree stems from </p>
  
  <p>(1) Building a minheap based on the frequency of each character in whatever file or string is being read in.</p>
  
  <p>(2) Popping off the 2 smallest values from the minheap and combining their weights into a new node.</p>
  
  <p>(3) Re-inserting the new node back into the same minheap.</p>
  
  <p>I'm confused about step 3. Most huffman trees I've seen have attributes more similar to a max heap than a minheap (although they are not complete trees). That is to say, the root contains the maximum weight (or combination of weights rather), while all of it's children have lesser weights. How does this implementation give a huffman tree when the combined nodes are put back into a minheap? I've been struggling with this for a while now. </p>
  
  <p>A similar question has already been posted here (with the same book as me): <a href="https://stackoverflow.com/questions/3269529/i-dont-understand-this-huffman-algorithm-implementation">I don&#39;t understand this Huffman algorithm implementation</a>  </p>
  
  <p>In case you wanted to see the exact function described in (3).</p>
  
  <p>Thanks for any help!</p>