If you squint just about right, you can probably see the equivalence between sorting plus queues and the tree based techniques. Especially if you use a tree-structured sorting algorithm.
That said, you generally have fixed frequencies with a predetermined set of constraints on the data, and you can determine the most common character frequency (or it's already known). I'm not sure how common this is in real-world applications of Huffman coding.
Seeing as you should only be building the tree once though, you're right--you'd be hard-pressed to tell the difference between the two approaches, barring implementation mistakes. Designing an implementation mistake that would cause noticeable differences is an exercise left to the reader.
I know what you're thinking: why not transform the tree into an Ahnentafel list and marshall it to a string containing only the alphabet characters in the appropriate slots, and use another chosen character to represent null slots, and write another implementation of the decoder that's driven off of the array? (Edit: Or, better still, transform it to a canonical Huffman codebook)
Yes, of course I could do that — and I actually want to. Alas, I have bigger fish to fry than writing the tree transformation code, the marshaling code, and the additional decoder implementation. So, when it's all said & done, according to the tradeoffs I was willing to make, my clients get to build the tree in O(n). I can tell that you're vexed that it worked out that way, but that's life.
I was just thinking about purely theoretical optima.