Relation between Code Length and Symbol Weight in a Huffman Code 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?"

Thanks!
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.