[pohl]

In my particular case, the character frequencies are (more or less) fixed and the sorting could be done ahead-of-time before feeding the leaf nodes into the first queue. So I really did get O(n) at instantiation time. However, my n is so small that it didn't matter much.

[eru]

You can also get fix your whole encoding then.

[pohl]

You can if it's absolutely fixed. But what about when it's only "more-or-less-fixed"? :-)

[eru]

Then you need the sorting, again. You can't have your cake and eat it, too.

[pohl]

Being able to relegate the cost of sorting to be a one-time cost on a server and allowing clients to build the tree they need for decoding in O(n) allows the client to [something about cake].

[eru]

I don't get it. If the probabilities are fixed, you might as well do the complete prepocessing on the server side.

[pohl]

I guess I chose to build the tree on the client side because the list of character frequencies is a fairly compact representation of the encoding, and I didn't want to serialize the whole tree and send it across the wire to the client. Are you suggesting that the client doesn't need the tree at all? If so, how would the client do the decoding? I confess I'm doing the naive crawling down the tree to the left or right as a 0 or 1 is read. Is there some other way the client could be doing this?

[eru]

Oops, horrible typo there.