I'm not sure if I should ask this here or over at StackOverflow (sorry if this is not the right place).

I'm constructing a Huffman code for a series of symbols with associated weights. I have a list of the code-lengths corresponding to each symbol, sorted by symbol weight (in non-decreasing order). Does it follow that this list is also sorted by code-length (in non-increasing order)?

I suspect that the answer is yes (since lower-weighted symbols will generally have shorter code lengths), but I'm not sure if this is guaranteed.

I guess what I really want to know is, "if a Huffman tree has two leaves a and b, where a had a higher weight than b, is b's code length always at least that of a's?"


  • $\begingroup$ does "weight" in this case mean frequency ? the code length according to a huffman code is almost exactly $\log(1/p_i)$, where $p_i$ is the normalized frequency. $\endgroup$ Jul 17, 2011 at 23:02
  • $\begingroup$ @Suresh: Yes, that's what I meant, sorry. How does one normalize a frequency? And why only "almost exactly"? $\endgroup$
    – Cameron
    Jul 17, 2011 at 23:09
  • $\begingroup$ @Cameron: you normalize the frequency $f_i$ by dividing it by the sum $n$ of the frequencies, so that to get $p_i=g_i/n\in [0,1]$ $\endgroup$
    – J..y B..y
    Jul 18, 2011 at 0:08
  • $\begingroup$ One comment: the code length in a Huffman code is not necessarily "almost exactly $\log 1/p_i$", although it is generally within a constant factor. $\endgroup$ Feb 8, 2016 at 2:22

1 Answer 1


Yes. A Huffman code is optimal. If a less frequent symbol had a shorter code length than a more frequent symbol, then you could get a code with better performance by exchanging them.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.